【C++】文字列をアルファベット順にソートするために並べ替えが必要な文字数を求める方法

問題概要

n 文字の文字列 S を考えます。S には小文字の英字のみが含まれています。ここで、0 以上 n 以下の範囲から整数 k を1つ選び、S から k 個の文字を選んで任意の順序に並べ替えます。このとき、選ばれなかった残りの文字は元の位置にそのまま留まります。この操作全体はちょうど一度だけ実行します。

目的は、操作後に S が完全にアルファベット順（辞書順）にソートされた状態となるような、k の値を求めることです。

例えば、入力が S = "acdb" の場合、出力は 3 になります。これは最初の文字 'a' がすでに正しい位置にあるため、残りの3文字（'c'、'd'、'b'）を並べ替えればよいからです。

解法のアプローチ

この問題は、次の手順で効率的に解くことができます。

1. 文字列 S のコピー d を作成し、d をソートします。これが「最終的に目指すべき完成形」です。
2. 元の文字列 S とソート済みの d を先頭から順に1文字ずつ比較します。
3. 位置が一致しない文字の個数 j をカウントします。
4. j の値を返します。これが求める k となります。

正しい位置に存在しない文字だけを選んで並べ替えれば文字列全体がソートされるため、不一致の文字数こそが答えになります。

擬似コード

n := S の長さ
d := S（コピーを作成）
d をソートする
j := 0
i = 0 から n - 1 まで繰り返し:
    もし S[i] != d[i] ならば:
        j を 1 増やす
j を返す

C++での実装例

実際のコードは以下のようになります。

#include <bits/stdc++.h>
using namespace std;

int solve(string S) {
    int n = S.size();
    string d = S;
    sort(d.begin(), d.end());
    int j = 0;
    for (int i = 0; i < n; i++) {
        if (S[i] != d[i])
            j++;
    }
    return j;
}

int main() {
    string S = "acdb";
    cout << solve(S) << endl;
}

実行結果

入力

"acdb"

出力

3

計算量の評価

この解法の時間計算量は、文字列のコピーとソートが支配的となるため O(n log n) です。また、コピー用の文字列 d を保持する必要があるため、空間計算量は O(n) となります。n が大きくなっても十分に高速に動作する、シンプルかつ実用的なアプローチです。