Given a string of 1’s and 2’s, standing at index ‘i’, you can move exactly two steps forward or backward if s[i]==2 , else you can move one step forward or backward if s[i] ==1. A string is called a good string if you can reach the end of the string by moving every index exactly once.
Now, you have been given two Strings A and B (not necessarily good), you have to return the number of possible sub-sequences of swaps available, such that both the strings become good.
Swap means you can swap A[i] with B[i].
Example:
A = 2211 B = 1111 ans = 8
please share your thought! UPD: N<=10^3
Constraints on length of A and B ?
I could be wrong, but I think it will never be beneficial to move back at all. Consider all 8 sequences of length 3 consisting of 1s and 2s. From what I can observe, the moving back thing can only be done for the sequence "221x" (where x is the next digit in the string)but again, moving back would be useless because going from 2->1->2->x,instead we can go from 2->1->x.
So I think we only need to move forward. Now the problem becomes that we need some 1s and 2s and we need to add upto n-1 (assuming zero based indexing).
Then, we can have dp[i][k][j][z]->which will store count of ways we can reach the end with A[i] = j and B[k] = z. There might be some impossible cases like, for eg, if A[i]=1 and B[k]=2, the states like dp[i][k][2][2] = 0. Final answer would be dp[n-1][n-1][j][z] sumed up over all values of j and z.