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; }

Try It