Longest Subsequence with equal 0s and 1s and all 0s earlier than all 1s


View Dialogue

Enhance Article

Save Article

Like Article

Given a binary string S, the duty is to search out the longest subsequence with that has equal variety of 0s and 1s and all of the 0s are current earlier than all of the 1s.

Examples:

Enter: S = “0011001111”
Output: 8
Clarification: By eradicating the third and 4th characters, the string turns into 00001111. 
That is the longest doable subsequence following the given circumstances.

Enter: S = “11001”
Output: 2
Clarification: The longest doable subsequence satisfying the circumstances is “01”

Enter: S = “111100”
Output: 0
Clarification: There is no such thing as a such subsequence that satisfies the circumstances.

 

 Strategy: The issue could be solved based mostly on the next thought:

For every index, we have to decide the utmost variety of 0s from the beginning and the utmost variety of 1s from the rear finish. This can maximize the size of the required subsequence.

Primarily based on the above thought, we have to do the next: 

  • For every index, calculate the entire variety of 0s from the beginning and the entire variety of 1s from the tip. 
  • If the 1s start from ith index then the entire size of the subsequence will probably be = 2 * min(0s from begin until i, 1s from finish until i)
  • The utmost of this for all indices is the reply.

Comply with the steps talked about under to implement the thought:

  • Construct two arrays (say pre[] and publish[]) to retailer the rely of 0s from the beginning and the rely of 1s from the tip.
  • Iterate from i = 0 to N-1:
    • If S[i] is 0, increment the rely of 0s and retailer it in pre[i].
  • Iterate from i = N-1 to 0:
    • If S[i] is 1, increment the rely 1s from finish and retailer it in publish[i].
  • Iterate the arrays from i = 0 to N-1:
    • Calculate the size of the subsequence if this index is the breaking level between 1s and 0s.
    • Most amongst these subsequences is the required size of the subsequence.

Beneath is the implementation of the above method.

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

int longestGoodString(string s)

{

    

    int n = s.measurement();

  

    

    

  

    

    

    vector<int> pre(n, 0), publish(n, 0);

  

    if (s[0] == '0')

        pre[0] = 1;

  

    

    for (int i = 1; i < n; i++) {

        if (s[i] == '0')

            pre[i] = pre[i - 1] + 1;

        else

            pre[i] = pre[i - 1];

    }

  

    if (s[n - 1] == '1')

        publish[n - 1] = 1;

  

    

    for (int i = n - 2; i >= 0; i--) {

        if (s[i] == '1')

            publish[i] = 1 + publish[i + 1];

        else

            publish[i] = publish[i + 1];

    }

  

    

    int ans = 0;

    for (int i = 0; i < n; i++) {

        ans = max(ans, 2 * min(pre[i], publish[i]));

    }

  

    

    return ans;

}

  

int most important()

{

    string S = "0011001111";

  

    

    cout << longestGoodString(S);

    return 0;

}

Time Complexity: O(N) the place N is the size of the String
Auxiliary Area: O(N) 

Leave a Reply