Given a binary string find the length of longest subsequence (NOT substring) which matches the regex 0*1*0*1*↵
↵
Here * means the preceding character can occur zero or more times.↵
↵
Eg input — 0101000, output — 6 (011000) ↵
Eg input — 0101 output — 4 (0101)↵
Constraint — Length of string = N < 10^5↵
↵
My approach:↵
↵
The valid string can be one of seven types:↵
↵
- 0 **only zeros** ↵
- 1 **only ones**↵
- 01 **some zeroes followed by some ones**↵
- 10 **some ones followed by some zeros**↵
- 010 **some zeros then some ones then some zeros**↵
- 101 **some ones then some zeros then some ones**↵
- 0101 **some zeros then some ones then some zeros and then some ones.**↵
↵
Now my dp[i][j] is the maximum length subsequence from **0** to **i** which forms the valid string of **jth** form where **0<=j<7**.↵
↵
My code : [link](https://pastebin.com/c8H6nCX2)↵
↵
Is this approach correct and if not can someone provide a test case where this might fail. Thankyou.↵
↵
P.S. This question was from a hiring test that is over now and I don't have the link to the problem.
↵
Here * means the preceding character can occur zero or more times.↵
↵
Eg input — 0101000, output — 6 (011000) ↵
Eg input — 0101 output — 4 (0101)↵
Constraint — Length of string = N < 10^5↵
↵
My approach:↵
↵
The valid string can be one of seven types:↵
↵
- 0 **only zeros** ↵
- 1 **only ones**↵
- 01 **some zeroes followed by some ones**↵
- 10 **some ones followed by some zeros**↵
- 010 **some zeros then some ones then some zeros**↵
- 101 **some ones then some zeros then some ones**↵
- 0101 **some zeros then some ones then some zeros and then some ones.**↵
↵
Now my dp[i][j] is the maximum length subsequence from **0** to **i** which forms the valid string of **jth** form where **0<=j<7**.↵
↵
My code : [link](https://pastebin.com/c8H6nCX2)↵
↵
Is this approach correct and if not can someone provide a test case where this might fail. Thankyou.↵
↵
P.S. This question was from a hiring test that is over now and I don't have the link to the problem.
