We have been given a binary string having 0s and 1s. We are also given a regex 0*1*0*1* where the * represents the no of occurrences of the corresponding base. The * can take arbitrary values. Here 00101111 is also a valid binary string and 0,1 are also valid strings.

We have to find the longest subsequence such that the subsequence satisfies the regex condition.

Constraints:

Test Cases 1<=T<=10^5

String Length 1<=L<=10^5

Sum of the length of string over all test cases would be <=10^6

For example:

a) 0101 has the longest subsequence of length 4.

b) 10101010 has the longest subsequence of length 5.

example b) can consider subsequences like 11101,00101,10001 and so on.

Can anybody help me solve this kind of problem? Please suggest me some similar kind of problems.

@l_returns @samarthtandon please help.