Table of Contents
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;
}