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.

Auto comment: topic has been updated by John_Cena (previous revision, new revision, compare).Anyone out there help

It's hard to check your DP transitions, but your states seems correct according to your formulation.

I have written my own DP — you can use a generator to stress-test the two solutions: Link

I tested it on 2-3 random small cases — the outputs matched.

Thank you so much.