Hi everyone.
The problem is given 3 strings I, S, F How many moves (it should be minimum) are needed to transform String I to string S and transform string S to string F.
A move on a string S consists of choosing two integers i, j (0 <= i <= j <= | S |) and inverting this substring. For example: S = ABCDE . If i = 1 and j = 4, the string will be DCBAE
Input:
The input consist of 3 strings I, S, F
|I| <= 10 **** |I| = |S| = |F|
Example:
abc cba cab
The output should be 2
I was trying to solve it using a BFS but I think it will get TLE because the worst case will exist N! strings and for every string I need to choose two elements to invert
Anyone have any idea how to solve it ? :D
Well you can always do it in at most 9 flips by putting the characters in place one at a time from beginning to end. Plus you could make some assumptions about order of flips to reduce the branching factor to about 19, and use some meet-in-the-middle so you only have to BFS to a depth of 4 from each side before giving up. It's feasible but pretty horrible so there's probably a better solution ¯_(ツ)_/¯
https://ideone.com/kE2v4c