Transform one string to another using minimum number of given operations


StringViews 3653

Given two strings s1 and s2, write a function that will convert s1 to s2(if possible) by using only one opeartion.

The operation is to pick any character from s1 and insert it at front of s1. Print the number of operations that took to convert.

Example

INPUT
s1 = “abcd”
s2 = “cbad”

OUTPUT
2
The number of opeartions took are 2

Explanation

Pick ‘b’ and insert it at beginning ie, “abcd” -> “bacd”
Pick ‘c’ and insert it at beginning ie, “bacd” -> “cbad”

Algorithm

1. First create two count arrays for s1 and s2, to check whether s1 can be converted to s2 or not

2. Traverse from end of both strings, ie, i = n-1 for s1 and j = n-1 for s2. Initialize count to keep track of no of operations

     a. If characters match, ie s1[i] == s2[j],  then make i = i-1 and j = j-1
     b. If current characters dont match, then search s2[j] in remaining s1, Keep increamenting     count as these characters must be moved ahead.

For above example, step 2 will be as follows

1) s1[i](ie, ‘d’) = s2[j](ie, ‘d’), decreament i,j

2) s1[i](ie, c) != s2[j](ie, ‘a’), decreament i and increase count, ie count = 1

3) s1[i](ie, ‘b’) != s2[j](ie, ‘a’), decreament i and increase count, count = 2

4) s1[i](ie, ‘a’) = s2[j](ie, ‘a’)

Therefore, count = 2

C++ Program

#include<bits/stdc++.h>
#define NO_OF_CHARS 256
using namespace std;
 
// Function to find minimum number of operations required to transform
// s1 to s2.
int minOps(string& s1, string& s2)
{
    int m = s1.length(), n = s2.length();
 
    //1) checking whether the conversion is possible or not
    if (n != m)
    {
       return -1;
    }
    int count[NO_OF_CHARS];
    //initializing 0 to every char in count.
    memset(count, 0, sizeof(count));
    // count characters in s1
    for (int i=0; i<n; i++)   
    {
       count[s2[i]]++;
    }
    // subtract count for every character in s2
    for (int i=0; i<n; i++)   
    {
       count[s1[i]]--;         
    }
    // Check if all counts become 0, if yes we are good
    for (int i=0; i<256; i++)   
    {
      if (count[i])
         return -1;
    }
 
    //2) calculating the number of operations required
    int ans = 0;
    for (int i=n-1, j=n-1; i>=0; )
    {
        // If there is a mismatch, then keep incrementing
        // 'count' until s2[j] is not found in s1[0..i]
        while (i>=0 && s1[i] != s2[j])
        {
            i--;
            ans++;
        }
 
        // If s1[i] and s2[j] match
        if (i >= 0)
        {
            i--;
            j--;
        }
    }
    return ans;
}
 
// Driver program
int main()
{
    string s1 = "abcde";
    string s2 = "cbad";
    cout << "Minimum number of operations required is " << minOps(s1, s2)<<endl;
    return 0;
}

Try It

 

Translate »