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
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.