 # NMK - Editorial

Author: Vaishnavi Chouhan
Tester: Rishabh Rathi

EASY-MEDIUM

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 -

1. Initialize steps as 0
2. 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.

# SOLUTIONS:

Setter's Solution (CPP)
``````#include<bits/stdc++.h>
using namespace std;

int steps(string& G, string& M) {
int n = G.length();

for (int i=n-1, j=n-1; i>=0; ) {

while (i>=0 && G[i] != M[j]) {
i--;
}

if (i >= 0) {
i--;
j--;
}
}
}

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 