C++で文字列を辞書順最小の部分文字列と残りに分割する方法

問題の概要

小文字のみで構成された長さnの文字列Sが与えられます。このとき、次の条件をすべて満たす2つの空でない部分文字列PとQを見つける必要があります。

• PとQはどちらもSの部分列である
• 各インデックスiについて、S[i]はPとQのどちらか一方にのみ属する
• Pはできるだけ辞書順で最小になる

例えば、入力が S = "thelightsaber" の場合、出力は "a, thelightsber" となります。文字列中で最も辞書順に小さい文字「a」をPとし、残りの文字をすべてQとすることで、条件を満たす分割が実現できるからです。

解法のアプローチ

この問題はシンプルな貪欲法で解くことができます。Pを辞書順最小にするには、Sに含まれる最小の文字を1文字だけPとして選び、残りのすべての文字をQに割り当てればよいのです。

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

1. 文字列Sのコピーcを作成し、cを昇順にソートする
2. ソート後のc[0](最小の文字)が元の文字列Sのどこに位置するかを調べ、その位置をaとする
3. Sからその位置の文字を1つ削除する
4. c[0](=P)と削除後のS(=Q)を出力する

C++による実装例

#include <bits/stdc++.h>
using namespace std;
void solve(string S){
    string c = S;
    sort(c.begin(), c.end());
    int a = S.find(c[0]);
    S.erase(S.begin() + a);
    cout << c[0] << ", " << S << endl;
}
int main(){
    string S = "thelightsaber";
    solve(S);
}

入力

"thelightsaber"

出力

a, thelightsber

コードの解説

このコードでは、まず文字列Sをコピーしてソートすることで、最小の文字「a」を特定しています。次に、find関数を使って元の文字列S内での「a」の位置を取得し、erase関数でその文字を削除します。最後に、最小の文字「a」と残りの文字列「thelightsber」を出力しています。

計算量については、ソートにO(n log n)、文字の検索と削除にO(n)かかるため、全体の計算量はO(n log n)となります。文字列の長さが大きくなっても効率的に動作する実装です。