We have been given a binary string having 0s and 1s. We are also given a regex 0101 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.
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
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.