This problem asks to handle strings, which is frequently required in competitive programming. If you couldn’t solve it, do learn it.

Replacing na with nya can be achieved by the following way, for example.

• Find a na with a for statement.
• Insert y between n and a of na you have found.

You can repeat this until you have no na. In both C++ and Python, you can use .insert() to insert strings.

We consider the complexity. .insert()-ing once costs a \(\mathrm{O}(N)\) time, so the overall complexity is \(\mathrm{O}(N^2)\).

Sample code (c++):

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    while(true) {
        bool fin = 1;
        for(int i = 0; i < (int)s.size() - 1; i++) {
            if(s.substr(i, 2) == "na") {
                s.insert(s.begin() + i + 1, 'y');
                fin = 0;
                break;
            }
        }
        if(fin) break;
    }
    cout << s << endl;
}

Sample code (Python):

n = int(input())
s = list(input())
while True:
    fin = 1
    for i in range(len(s) - 1):
        if s[i] == "n" and s[i + 1] == "a":
            s.insert(i + 1, "y")
            fin = 0
            break
    if fin:
        break
print("".join(s))

A wise reader may notice that this problem can actually be solved in a total of \(\mathrm{O}(N)\) time.

Due to the internal structure of an array or a list, appending an element to the tail is fast, while inserting elsewhere is slow, so we want to accomplish it only by appending. You can do in a way as shown in the following sample code.

Sample code (Python):

n = int(input())
s = list(input())
ans = []
for i in range(n):
    if i >= 1 and ans[-1] == "n" and s[i] == "a":
        ans.append("y")
    ans.append(s[i])
print("".join(ans))