find minimum steps required to change one binary string to another

Question

Given two string str1 and str2 which contain only 0 or 1, there are some steps to change str1 to str2,

step1: find a substring of str1 of length 2 and reverse the substring, and str1 becomes str1' (str1' != str1)

step2: find a substring of str1' of length 3, and reverse the substring, and str1' becomes str1'' (str1'' != str1')

the following steps are similar.

the string length is in the range [2, 30]

Requirement: each step must be performed once and we can not skip previous steps and perform the next step.

If it is possible to change str1 to str2, output the minimum steps required, otherwise, output -1

Example 1

str1 = "1010", str2 = "0011", the minimum step required is 2

first, choose substring in range [2, 3], "1010" --> "1001",

then choose substring in the range [0, 2], "1001" --> "0011"

Example 2

str1 = "1001", str2 = "0110", it is impossible to change str1 to str2, because in step1, str1 can be changed to "0101" or "1010", but in step3, it is impossible to change a length3 substring to make it different. So the output is -1.

Example 3

str1 = "10101010", str2 = "00101011"， output is 7

I can not figure out example 3, because there are two many possibilities. Can anyone gives some hint on how to solve this problem? What is the type of this problem? Is it dynamic programming?

Answer 1

This is in fact a dynamic programming problem. To solve it, we are going to try all possible permutations, but memoize the results along the way. It could seem that there are way too many options - there are 2^30 different binary strings of length 30, but keep in mind that reverting a string doesn't change number of zeroes and ones we have, so the upper bound is in fact 30 choose 15 = 155117520 when we have a string of 15 zeroes and ones. Around 150 million possible results is not too bad.

So starting with our start string, we are going to derive all possible string from each string we derived so far, until we generate end string. We are also going to track predecessors to reconstruct generation. Here's my code:

start = '10101010'
end = '00101011'

dp = [{} for _ in range(31)]
dp[1][start] = '' # Originally only start string is reachable

for i in range(2, len(start) + 1):
  for s in dp[i - 1].keys():
    # Try all possible reversals for each string in dp[i - 1]
    for j in range(len(start) - i + 1):
      newstr = s
      newstr = newstr[:j] + newstr[j:j+i][::-1] + newstr[j+i:]
      dp[i][newstr] = s
  if end in dp[i]:
    ans = []
    cur = end
    for j in range(i, 0, -1):
      ans.append(cur)
      cur = dp[j][cur]
    print(ans[::-1])
    exit(0)

print('Impossible!')

And for your third example, this gives us sequence ['10101010', '10101001', '10101100', '10100011', '00101011'] - from your str1 to str2. If you check differences between the strings, you'll see which transitions were made. So this transformation can be done in 4 steps rather than 7 like you suggested.

Lastly, this will be a bit slow for 30 in python, but if you rewrite it into C++, it's going to be a couple of seconds tops.