find minimum steps required to change one binary string to another

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.

This Question can be solved using Backtracking. here is my C++ Code, Which runs smooth with my testcases. This Question Came in an OA of Persistent systems and i was a bit confused about the steps, but this is simple Backtracking. Wants your suggestions if Dp can Optimize my solution!.

//prabaljainn
#include <bits/stdc++.h>
using namespace std;
string s1,s2;
int ans=1e9; int n;

void rec(string s1,int level){
    if(s1==s2){
        ans = min(ans,level-2);
        return;
    }

    for(int i=0; i<= n-level; i++){
        reverse(s1.begin()+i, s1.begin()+i+level);
        rec(s1,level+1);
        reverse(s1.begin()+i, s1.begin()+i+level);
    }
}

int main(){

  cin>>s1>>s2;
  n = s1.size();
  rec(s1,2);
  if(ans==1e9)
      cout<<"-1"<<endl;
  else
  cout<<ans<<endl;
}

Happy coding

This problem can be solved using breadth-first search. The following solution uses a queue which stores a pair having the current string as the first member and current operation length(initially 2) as the second member. A set is used to store already visited strings to prevent entering redundant states. For current string, we reverse every substring of length k where k is current operation length and add it to the queue if it hasn't been seen before. If the current string equals the desired string then answer is 'current operation length-2'. If queue becomes empty, then the answer isn't possible.

string str1,str2;
cin>>str1>>str2;

queue<pair<string, int>> q;
set<string> s;

q.push({str1,2});
s.insert(str1);
while(!q.empty())
{
    auto p=q.front();
    q.pop();
    if(p.first==str2)
    {
        cout<<p.second-2;
        return 0;
    }
    if(p.second<=p.first.size())
    {
        for(int i=0;i<=p.first.size()-p.second;i++)
        {
            string x=p.first;
            reverse(x.begin()+i,x.begin()+i+p.second);
            if(s.find(x)==s.end())
            {
                q.push({x,p.second+1});
                s.insert(x);
            }

        }
    }
}
cout<<-1;

save str1 as start of BFS and at each step,reverse values of all substrings of length 2 and 3 and see if the new strings formed after reversing have been seen previously or not.....if not seen....push them in the queue and also maintain count of steps...if the string at the front of queue is str2 at any time...that step is the answer