I used state machine concept. Identified 5 different states using two character combination.
See this in my solution
Explaination:
State is represented by two state variables a and b.
if the string is ending at b then a is zero (to indicate
the end state). If a is not zero then a and b represent
the last two point (character) states when b is
not the end point, but a is the end point.
So (0, 1) and (0, 2) means the good string is ending at character 1
and 2 respectively.
The valid states can be
(2, 1) when it is like (***21) and from b(1) the dog can jumps to
a(2) and so a(2) is the end point, not the last character b(1).
(2, 2) when it is like (**22) and dog is at the a(2) and b(2) is
unvisited character.
So moving to next character is like state transition, this will be
clear by following example:
String is in state (0, 1) and the next character is ‘2’, then the new
state would be (0, 2).
Current state is (2, 1) and the next character is ‘2’, the new state
would be (0, 2).
Current state is (2, 1) the the next character is ‘1’ then the new
state would be (0, 1).
Current state is (2, 2) and the next character is ‘1’ then the new state
would be (2, 1).
After determining the condition for a good string, I used dp[i][j][k] where i denotes the current position, j denotes the state of first string and k denotes the state of second string. State of a string is either “free” (next letter can be either 1 or 2), “open” (there is a single 2 and thus the next letter must be 2) and “closed” (there was a pair of 2s before so the i-th lettter must be 1). The state transitions are not hard once you get this idea.
The logic being that at any index i, if ai=bi then we don’t need to look out for anything. Now we divide the two strings into partitions - each partition [i,j] such that ai=bi and aj=bj and ak≠bk for k belonging to (i,j). In such partitions we can derive some conditions based on observed pattern. These conditions fulfill all the requirements of a ‘good’ string. The conditions are clearly written in my solution.
The problem was an ad-hoc one, with no special prerequisite.
By making some “good strings” manually you can easily see that following two conditions should be hold-
always exactly two “2” will come together eg. 1221 but not “2222 or 1211”.
always second last digit of strings should be “1”.
Now after determining these conditions you just have to form a dynamic programming solution in which at each index you have two choices , either swap the corresponding digits or don’t.
here is the link of my solution my_solution .
P.S. I took digits “0 and 1” instead of “1 and 2” in my solution .
My solution did not pass all test cases only 6 but still my approach was as follows
I identified some conditions the string must satisy to be a good string.
second last element of the string must be 1, if 2 it is a bad string
2 cannot appear independently it must always appear as 221 (except as last element)
So what I did was I looped through a[i] & b[i] dividing the elements into ‘N’ segments
(a[p],b[p])->(a[q],b[q])
such that they are isolated by a[p-1]=b[p-1]=1 and a[q+1]=b[q+1].122122112211-> 112211221221
each such segment can have 2 ways of swapping their elements.
So n such elements have pow(2,N) ways of swapping.
Also count the no: places where a[i]=b[i] as countident.
elements at identical places can be swapped in pow(2,countident) ways
So final answer=pow(2,N+countident)
Also make sure that in cases where a[i]=b[i]=2,a[i+1]=b[i+1]=2,a[i+2]=b[i+2]=1 both countident and N will count them so that condition must be checked seperately.
