C++で各接頭辞の「a」と「b」の個数が等しくなるよう文字列を更新する方法

長さ n（偶数）の文字列 S があるとします。S には「a」と「b」の2種類の文字のみが含まれており、この文字列を修正して、あらゆる長さの接頭辞（先頭から連続する部分文字列）において「a」と「b」の出現回数が等しくなるようにしたいと考えています。

このとき許される操作は、「文字列中の任意の位置を選び、その位置の文字をもう一方の文字（a→b、b→a）に置き換える」というものです。この操作は何度実行しても構いません。最終的に得られた文字列を返してください。

例として、入力が S = "aabbbb" の場合、出力は "baabab" となります。

解法のアプローチ

この問題を効率的に解く鍵は、文字列を「隣り合う2文字ずつのペア」に分けて考えることです。各ペアの中に「a」と「b」が1つずつ含まれていれば、すべての接頭辞で両者の個数が等しくなることが保証されます。したがって、ペア内の2文字が同じである場合にのみ、どちらか片方をもう一方の文字へ置き換えればよいのです。

具体的な手順は以下のとおりです。

• 文字列の長さを n とします。
• i を 0 から開始し、i < n を満たす間、2 ずつ増やしながらループします。
• S[i] と S[i+1] が同一の文字であれば、置換回数を 1 増やし、S[i] を反対の文字に書き換えます。
• ループ終了後、更新された文字列 S を返します。

n := size of S
for initialize i := 0, when i < n, update i := i + 2, do:
    if S[i] is same as S[i + 1], then:
        (increase ans by 1)
    S[i] := (if S[i] is same as 'a', then 'b', otherwise 'a')
return S

C++による実装例

理解を深めるために、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
string solve(string S){
    int n = S.size(), ans = 0;
    for (int i = 0; i < n; i += 2)
        if (S[i] == S[i + 1]){
            ans++;
            S[i] = S[i] == 'a' ? 'b' : 'a';
        }
    return S;
}
int main(){
    string S = "aabbbb";
    cout << solve(S) << endl;
}

入力

"aabbbb"

出力

baabab

このアルゴリズムの計算量は O(n) であり、文字列を一度走査するだけで目的の文字列が得られるため、非常に効率的です。