# PROBLEM LINK: Naamkaran

* Author:* Vaishnavi Chouhan

*Rishabh Rathi*

**Tester:**# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

String

# PROBLEM:

You are given two **nice strings** - G and M. Two strings are **nice**, if the letters are the same but the order is different.

We have to convert G to M. The only operation allowed is to pick any character from G and insert it at front.

Find the **minimum number of steps** required to convert string G to M.

**NOTE** : In one step, one letter of string G is added at the front of string G. In every subsequent step, the string formed in the previous step is used for operation.

# EXPLANATION:

Let us suppose that length of G = length of M = N.

For transforming G to M, start matching from last characters of both strings. If last characters match, then our task reduces to N-1 characters. If last characters don’t match, then find the position of M’s mis-matching character in G.

The **difference** between two positions indicates that these many characters of G must be moved before current character of G.

Below is complete algorithm -

- Initialize steps as 0
- Start traversing from end of both strings
- If current characters of G and M
**match**, i.e., G[i] = M[j], then do i = i-1 and j = j-1 - If current characters
**don’t match**, then search M[j] in remaining G.

While searching, keep incrementing steps as these characters must be moved ahead for G to M transformation.

- If current characters of G and M

# SOLUTIONS:

## Setter's Solution (CPP)

```
#include<bits/stdc++.h>
using namespace std;
int steps(string& G, string& M) {
int n = G.length();
int answer = 0;
for (int i=n-1, j=n-1; i>=0; ) {
while (i>=0 && G[i] != M[j]) {
i--;
answer++;
}
if (i >= 0) {
i--;
j--;
}
}
return answer;
}
int main() {
string G; cin>>G;
string M; cin>>M;
int number_of_steps = steps(G, M);
cout<<number_of_steps<<endl;
if(number_of_steps<5)
cout<<M;
else
cout<<G;
return 0;
}
```

## Tester's Solution (Python)

```
def solve(g, m):
ans = 0
n = len(g)
i = j = n-1
while(i>=0):
while(i>=0 and g[i] != m[j]):
i -= 1
ans += 1
if i>=0:
i -= 1
j -= 1
return ans
g = input()
m = input()
moves = solve(g, m)
if moves<5:
ans = m
else:
ans = g
print(moves)
print(ans)
```

Feel free to share your approach. In case of any doubt or anything is unclear, please ask it in the comments section. Any suggestions are welcome