Longest non-increasing subsequence in a binary string

In this problem, we need to find the longest non-increasing subsequence of a given string.

Non-increasing means that the characters are either the same or in descending order. Since binary strings only contain "0" and "1", the resulting string should either start with "1" and end with "0", or start and end with "0" or "1".

To solve this problem, we will count the prefix "1" and suffix "0" at each position of the string, and find the maximum sum of the prefix "1" and the suffix "0".

Problem Statement - We are given a binary string str. We need to find the longest non-increasing subsequence from the given string.

Example

Input –  str = "010100"

Output – 4

illustrate

The longest non-increasing subsequence is "1100".

Input –  str = "010110010"

Output – 6

illustrate

The longest non-increasing subsequence is "111000".

Input –  str = ‘00000000’

Output – 8

illustrate

The longest non-increasing subsequence is '00000000', which is equal to the given string.

method 1

In this method we will store the count of prefix "1" and suffix "0" in the array for each index. After that, we get the values ​​from the same index in both arrays, add them, and find the maximum sum.

algorithm

• Step 1 - Define pre1s and suffix0s arrays to store prefix 1 and suffix 0. Additionally, initialize all array elements to 0.

• Step 2 - Use a for loop to iterate through the string and calculate the prefix 1 for each index. If i > 0, then the value of the previous element is added to the current element.

• Step 3 - If the current character is "1", add 1 to the current value of pre1s[i].

• Step 4 - Now, count the suffix 0s in the given string. Traverse the string starting from the end.

• Step 5 - If the value of "I" is not equal to "n – 1", get the value of the "I 1" element and add it to the current element.

• Step 6 - If the current element is "0", add 1 to the current element.

• Step 7 - Now, initialize the "res" variable with 0.

• Step 8 - Iterate over "pre1s" and "suffix0s" using a loop.

• Step 9 - Get the value from the i-th index in the "pre1s" and "suffix0s" arrays and add them together. Additionally, if "sum" is greater than the current value of the "res" variable, the "res" variable value is changed with the "sum" value.

• Step 10 - Return the value of the "res" variable.

Example

For input '010100', the prefix array is [0, 1, 1, 2, 2, 2], and the suffix 0 array is [4, 3, 3, 2, 2, 1]. The sum array will be [4, 4, 4, 4, 4, 1] and the maximum value in the sum array is 4. Therefore, the answer will be 4.

#include <bits/stdc++.h>
using namespace std;
int getMaxLength(string str, int n){
   // To store the prefix count of '1's and suffix count of '0's
   int pre1s[n] = {0},
      suffix0s[n] = {0};
   for (int i = 0; i < n; i++){
   
      // get the prefix count of '1's
      if (i > 0){
         pre1s[i] += pre1s[i - 1];
      }
      
      // If the current character is '1', then update the pre1s array by adding 1; else, keep it as it is.
      if (str[i] == '1'){
         pre1s[i] += 1;
      }
   }
   
   // get suffix count of '0's
   for (int i = n - 1; i >= 0; i--) {
   
      // add the suffix count of '0's
      if (i != n - 1)
         suffix0s[i] += suffix0s[i + 1];
         
      // If the current character is '0', then update the suffix0s array by adding 1; else, keep it as it is.
      if (str[i] == '0')
         suffix0s[i] += 1;
   }
   
   // to store the final result value
   int res = 0;
   
   // iterate over the pre1s[] and suffix0s[] array and find the maximum value of pre1s[i] + suffix0s[i]
   for (int i = 0; i < n; i++){
      res = max(res, pre1s[i] + suffix0s[i]);
   }
   
   // Return the result
   return res;
}

// Driver Code
int main(){
   string str = "010100";
   int N = str.length();
   cout << "The length of the longest non-increasing subsequence in the given binary string is - " << getMaxLength(str, N);
   return 0;
}

Output

The length of the longest non-increasing subsequence in the given binary string is - 4

Time complexity - O(N), because we need to initialize the array with prefix 1 and suffix 0.

Space complexity - O(N) since we store prefix 1 and suffix 0 in array

Method 2

In this method, we will first count the total number of zeros. After that, we start iterating through the string, continuing to count "1"s, and if 0 is found, decrementing it by "0"s. Additionally, we add the counts of 0 and 1 in each iteration and find the maximum resulting value.

algorithm

• Step 1 - Define the 'count1', 'count0' and 'res' variables and initialize them with 0 to store the count of 1, 0 and the final result respectively.

• Step 2 - Count the total number of zeros by looping through the string and storing it in the "count0" variable.

• Step 3 - Now, iterate over the string using a loop.

• Step 4 - In the loop, if the current character is "1", increase the value of "count1" by 1, otherwise decrease the value of "count0" by 1.

• Step 5 - Additionally, store the maximum value from "res" and "count0 count1" into the "res" variable.

• Step 6 - When the loop terminates, return the value of the "res" variable.

Example

#include <bits/stdc++.h>
using namespace std;
int getMaxLength(string str, int n){
   int count1 = 0, count0 = 0;
   int res = 0;
   // counting total zeros in the string
   for (int i = 0; i < n; i++){
      if (str[i] == '0')
         count0++;
   }
   
   // counting 1s from left, subtracting zeros from total zeros and adding both counts.
   for (int i = 0; i < n; i++){
      if (str[i] == '1')
         count1++;
      else
         count0--;
      res = max(res, count1 + count0);
   }
   return res;
}
int main(){
   string str = "010110010";
   int N = str.length();
   cout << "The length of the longest non-increasing subsequence in the given binary string is - " << getMaxLength(str, N);
   return 0;
}

Output

The length of the longest non-increasing subsequence in the given binary string is - 6

Time complexity - O(N), since we count the total number of zeros in the string and traverse the string to find the longest subsequence.

Space complexity - O(1)

in conclusion

Here, both methods have the same time complexity but different space complexity. The second method uses constant space when we optimize the code, but the first method uses dynamic space to store the total number of prefix 1 and suffix 0.

The above is the detailed content of Longest non-increasing subsequence in a binary string. For more information, please follow other related articles on the PHP Chinese website!