はまやんはまやんはまやん

hamayanhamayan's blog

Permutation and Palindrome [February Challenge 2018 C]

https://www.codechef.com/FEB18/problems/PERMPAL

長さNの文字列Sがある。
これについて、要素数Nの順列Pを作る。
「P[i] := P[i]文字目をi番目に持ってくる」という操作をすると、結果が回文となる順列Pを求めよ。
もし、回文を作れないなら"-1"

解法

https://www.codechef.com/viewsolution/17299649

まず、「文字毎に文字数を数えた時に文字数が奇数である文字が1個以下なら回文が作れる」という性質を思い出そう。
なので、「cnt[c] := 文字cが何個あるか」を作って、奇数個が2個以上なら"-1"を返そう。
あとは、回文を作るのだが、スワップする前にbufを作ろう。
buf[c] := 文字列Sで文字cがある添字のキュー
これを作ったら、cntを使いながら回文を構築する。
回文から順列を作るにはbufで何番目かを順番に使っていけば求まる。

string S;
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> S;
    int n = S.length();

    map<char, int> cnt;
    fore(c, S) cnt[c]++;

    int odd = 0; char oddc;
    fore(p, cnt) if (p.second % 2 == 1) odd++, oddc = p.first;
    if (1 < odd) {
        printf("-1\n");
        return;
    }

    map<char, queue<int>> buf;
    rep(i, 0, n) buf[S[i]].push(i + 1);

    int idx = 0;
    fore(p, cnt) {
        if (p.second % 2 == 1) {
            S[n / 2] = p.first;
            p.second--;
        }
        while (p.second) {
            S[idx] = S[n - 1 - idx] = p.first;
            p.second -= 2;
            idx++;
        }
    }

    rep(i, 0, n) {
        if (i) printf(" ");
        int ans = buf[S[i]].front(); buf[S[i]].pop();
        printf("%d", ans);
    }
    printf("\n");
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T;  cin >> T;
    rep(t, 0, T) solve();
}