「trygub」が部分列として現れない文字列を作るC++コード

n個の小文字の英字からなる文字列Sが与えられたとします。このとき、Sの文字を並べ替えて、結果の文字列の中に「trygub」が部分列(subsequence)として含まれないようにする必要があります。

たとえば、入力が S = "pintontrygubabc" の場合、出力は "abbcginnoprttuy" となります。

解法のアプローチ

この問題は驚くほどシンプルで、以下の手順だけで解決できます。

• 文字列Sを昇順(アルファベット順)にソートする
• ソートした結果をそのまま返す

なぜソートするだけで良いのか?

文字列を昇順にソートすると、すべての「b」が先頭側に集まり、「t」「r」「y」「g」「u」はそれより後ろに配置されます。「trygub」が部分列になるには、t → r → y → g → u → b という順序で文字が出現する必要がありますが、ソート後は最後の「b」が必ず他の文字より前に来てしまうため、この順序は絶対に成立しません。したがって、ソートされた文字列は常に条件を満たすことが保証されます。

実装例

それでは、実際のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
string solve(string S){
    sort(S.begin(), S.end());
    return S;
}
int main(){
    string S = "pintontrygubabc";
    cout << solve(S) << endl;
}

入力

"pintontrygubabc"

出力

"abbcginnoprttuy"

このように、標準ライブラリの sort を使うことで、計算量 O(n log n) で簡単に問題を解くことができます。特別なデータ構造や複雑なロジックは一切不要です。