まず、各色 \(i = 1, 2, \ldots, M\) に対して、 \(S\) の 色 \(i\) で塗られた文字全ての位置を昇順に格納した可変長配列 \(P^{(i)}\) を作ります。

\(S\) を \(1\) 回走査することで \(P^{(1)}, P^{(2)}, \ldots, P^{(M)}\) 全てを同時に \(O(N)\) 時間で作ることができます。 具体的には、可変長配列 \(P^{(1)}, P^{(2)}, \ldots, P^{(M)}\) がすべて空の状態からはじめ、 \(S\) の各添字 \(i = 1, 2, \ldots, N\) についてこの順番に見ていき、可変長配列 \(P^{(C_i)}\) の末尾に \(i\) を追加するという処理を行えば良いです。

\(P^{(1)}, P^{(2)}, \ldots, P^{(M)}\) を用いて、出力すべき答えである長さ \(N\) の文字列 \(T\) の各文字が下記の通りにわかります。

• \(P^{(1)} = (p^{(1)}_1, p^{(1)}_2, \ldots, p^{(1)}_{k_1})\) とおく。\(T\) の \(p^{(1)}_2, \ldots, p^{(1)}_{k_1}, p^{(1)}_1\) 文字目が、それぞれ \(S\) の \(p^{(1)}_1, p^{(1)}_2, \ldots, p^{(1)}_{k_1}\) に等しいとわかる。

• \(P^{(2)} = (p^{(2)}_1, p^{(2)}_2, \ldots, p^{(2)}_{k_2})\) とおく。\(T\) の \(p^{(2)}_2, \ldots, p^{(2)}_{k_2}, p^{(2)}_1\) 文字目が、それぞれ \(S\) の \(p^{(2)}_1, p^{(2)}_2, \ldots, p^{(2)}_{k_2}\) に等しいとわかる。

• \(\cdots\)

• \(P^{(M)} = (p^{(M)}_1, p^{(M)}_2, \ldots, p^{(M)}_{k_M})\) とおく。\(T\) の \(p^{(M)}_2, \ldots, p^{(M)}_{k_M}, p^{(M)}_1\) 文字目が、それぞれ \(S\) の \(p^{(M)}_1, p^{(M)}_2, \ldots, p^{(M)}_{k_M}\) に等しいとわかる。

以下に、C++ 言語による本問題の正解例を記載します。

#include <iostream>
#include <vector>
using namespace std;

int n, m;
string s;
int c[200000];
vector<int> p[200001];

int main(void)
{
    cin >> n >> m;
    cin >> s;
    for(int i = 0; i < n; i++) cin >> c[i];
    for(int i = 0; i < n; i++) p[c[i]].push_back(i);
    
    string t(n, '?');
    for(int i = 1; i <= m; i++){
        int k = p[i].size();
        for(int j = 0; j < k; j++) t[p[i][(j+1)%k]] = s[p[i][j]];
    }
    cout << t << endl;
    
    return 0;
}