BINSUBS- Unofficial editorial

editorial
1

Hello Everyone,

This is an approach which I used for solving BINSUBS in January Lunchtime. I think I might help beginners’ understand the solution using simpler method.

As we know that input string is binary(consist of only 0s and 1s), we keep two variables l0 and l1. These two variables tells us the longest subsequence ending at 0 and 1 respectively. For a subsequence to be increasing, there can be two cases.

  1. If current character is ‘0’, then we can only jump from a ‘0’, as jumping from ‘1’ to ‘0’ makes a decreasing step.
  2. If current character is ‘1’, then we can jump from either ‘0’ or ‘1’, as in both cases we get increasing subsequence (i.e. 01 or 11). So here we would consider largest value we can get by jumping from either 0 or 1 to current index value 1.

Now l0, l1 would give us the length of longest increasing subsequence ending at 0 and 1 respectively. The question asks us to minimize the number of characters to be removed from original string to get increasing subsequence, therefore we consider the larger out of l0 and l1 and substract it from original length. That gives us the minimum characters to be removed to get increasing subsequence in original string.

Time taken: O(n)

Code:

int main() {
// your code goes here
int t;  cin >> t;
while(t--)
{
    int n;   cin >> n;
    string s;   cin >> s;
    
    int l0=0, l1=0;            //length of subsequence ending at 0 and 1
    for(int i=0;i<n;i++)
    {
        if(s[i] == '0')       //if current character is 0
        {
            l0=l0+1;           //subseq length would 1 + subseq length ending at 0
        }
        else
        {
            l1=max(l0, l1)+1;     //subseq length would 1 + max(subseq length ending at 0, subseq length ending at 1)
        }
    }
    cout << min(n-l0, n-l1) << endl;
}

return 0;

}

Bonus: If the string is ternary instead of binary string. Then we can again implement solution in O(n) approach by considering three variables l0, l1 and l2.

2 Likes
2

ok