Strings: Find minimum operations required to transform a string into another string

Problem Statement:

You are given 2 strings, you need to convert str1 to str2 by only moving a character from str1 to front.

If the string can be transformed, then return the min number of operations required.

Example

Str 1 = ADCB
Str 2 = ABCD

Output: 3

Move C to the front -> CADB
Move B to the front —> BCAD
Move A to the front —> ABCD

Solution

Solution is simple.

First check if both of the stringlength are same and also character set is also same. If they are same then move to next step.

We traverse from end of both of the strings and if the character matches, then we decrement from both of the strings and then compare again.

If theya re not same, then we searh the char of s2 in s1 and keep incrementing till we get a matching character in s1. This will be our count.

Example:

s1 = "ABCD"
s2 = “CBAD”

Pass 1:
s1 = D, s2 = D

Pass 2:

s1 = C, s2 = A
They do not match, so decrement s1 and then increment count by 1.

Pass 3:
s1 = B, s2 = A
They do not match, so decrement s1 and then increment count by 2.

Pass 3:
s1 = A, s2 = A
They match, so the result is 2.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 
#include <queue> 

using namespace std;

int get_min_ops(string& A, string& B)
{
    int m = A.length();
    int n = B.length();
 
    if (n != m)
       return -1;

    int count[256];
    memset(count, 0, sizeof(count));

    //count the number of char in B
    for (int i=0; i<n; i++) 
       count[B[i]]++;

     //remove those characters in A
    for (int i=0; i<n; i++) 
       count[A[i]]--;     

     // check if all the counts are 0, if not, it means
     // there are different set of characters and return -1;
    for (int i=0; i<256; i++)  
      if (count[i])
         return -1;
 
    int res = 0;
    for (int i=n-1, j=n-1; i>=0; )
    {

        while (i>=0 && A[i] != B[j])
        {
            i--;
            res++;
        }
 
        if (i >= 0)
        {
            i--;
            j--;
        }
    }
    return res;
}
 
int main()
{
    string A = "ABCD";
    string B = "CBAD";
    cout << "Minimum number of operations required is " << get_min_ops(A, B);
    return 0;
}

Output:

Minimum number of operations required is 2