この問題は、文字列を扱う問題です。文字列の操作は競プロで頻出なので、解けなかった方はぜひ学んでみましょう。

na を nya で置き換える操作は、例えば以下の方法で実現できます。

• for ループを用いて na を \(1\) つ見つける。
• 見つけた na の n と a の間に y を挿入する。

上記の方法を na が見つからなくなるまで繰り返せばよいです。文字列の挿入には .insert() が c++ でも python でも使えます。

計算量を考えます。.insert() を \(1\) 回行うのにかかる計算量は \(\mathrm{O}(N)\) なので、全体で \(\mathrm{O}(N^2)\) となります。

実装例(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;
}

実装例(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))

聡明な読者の方はお気づきかもしれませんが、この問題は実は \(\mathrm{O}(N)\) で解くこともできます。

配列やリストの都合上、末尾に追加するのは高速ですが、途中に挿入するのは遅いので、末尾への追加のみを用いて上の方法を行いたいです。これは以下の実装例に示す方針で可能です。

実装例(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))