NMK - Editorial

editorial
, ,
1

PROBLEM LINK: Naamkaran

Author: Vaishnavi Chouhan
Tester: Rishabh Rathi

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 -

  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();
	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 :smile: