Longest Non-Increasing Subsequence in a Binary String

Longest Non-Increasing Subsequence in a Binary String

Given a binary string S of size N, the task is to find the length of the longest non-increasing subsequence in the given string S.

Examples:

Input: S = “0101110110100001011”
Output: 12 
Explanation: The longest non-increasing subsequence is “111111100000”, having length equal to 12.

Input: S = 10101
Output: 3

Approach: The given problem can be solved based on the observation that the string S is a binary string so a non-increasing subsequence will always consist of 0 with more consecutive 1s or 1 with more consecutive 0s. Follow the below steps to solve the problem:

• Initialize an array, say pre[], that stores the number of 1s till each index i for i over the range [0, N – 1].
• Initialize an array, say post[], that stores the number of 0s till each index i to the end of the string for i over the range [0, N – 1].
• Initialize a variable, say ans that stores the length of the longest non-increasing subsequence in the given string S.
• Iterate over the range [0, N – 1] and update the value of ans to the maximum of ans and (pre[i] + post[i]).
• After completing the above steps, print the value of ans as the result.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    int findLength(string str, int n) {               int pre[n], post[n];             memset(pre, 0, sizeof(pre));     memset(post, 0, sizeof(post));                  for (int i = 0; i < n; i++) {                     if (i != 0) {             pre[i] += pre[i - 1];         }                              if (str[i] == '1') {             pre[i] += 1;         }     }                  for (int i = n - 1; i >= 0; i--) {                     if (i != n - 1)             post[i] += post[i + 1];                              if (str[i] == '0')             post[i] += 1;     }             int ans = 0;                  for (int i = 0; i < n; i++) {         ans = max(ans, pre[i] + post[i]);     }             return ans; }    int main() {     string S = "0101110110100001011";     cout << findLength(S, S.length());        return 0; }

Output:

12

Time Complexity: O(N)
Auxiliary Space: O(N)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets