C++で解く整然キュー（Orderly Queue）問題：辞書順最小の文字列を求めるアルゴリズム

問題の概要

小文字のみで構成される文字列 S が与えられます。この文字列に対して、任意の回数だけ次の操作を行うことができます。

操作： 先頭の K 文字の中から1文字を選び、それを取り除いて文字列の末尾に移動させる。

このとき、操作を何度行ってもよいとして、最終的に得られる文字列のうち辞書順で最小のものを求めてください。

例えば、入力が "cabaa"、K = 3 の場合、答えは "aaabc" になります。

解き方のアプローチ

ケース1：K > 1 の場合

Kが2以上のときは、実質的にどのような並べ替えも可能になります。これは、隣接する2文字の入れ替え（バブルソートと同じ要領）を繰り返すことで任意の順列が構成できるためです。したがって、以下の手順で答えが得られます。

• 文字列 S をソートする

• ソート結果をそのまま返す

ケース2：K = 1 の場合

Kが1のときは、常に先頭の1文字しか末尾に移動できません。つまり、操作によって文字列を回転させることしかできないため、考えられるすべての回転を試し、その中で最も小さい文字列を採用します。

アルゴリズムの手順

• ret := S（初期値として元の文字列を設定）

• n := 文字列 S の長さ

• i := 1 から n 未満の間、i を1ずつ増やしながら以下を繰り返す：

  • S := S の先頭の1文字を切り取り、末尾に追加する（1回転）

  • もし S < ret であれば、ret = S と更新する

• 最後に ret を返す

それでは、以下の実装例を見て理解を深めましょう。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string orderlyQueue(string S, int K) {
        if(K > 1){
            sort(S.begin(), S.end());
            return S;
        }
        string ret = S;
        int n = S.size();
        for(int i = 1; i < n; i++){
            S = S.substr(1) + S.substr(0, 1);
            if(S < ret) ret = S;
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.orderlyQueue("cabaa", 3));
}

入力

"cabaa", 3

出力

aaabc

計算量について

K = 1 の場合： 回転を最大 n 回行い、毎回の文字列比較に O(n) かかるため、全体の時間計算量は O(n²) となります。

K > 1 の場合： 処理はソートが支配的となるため、時間計算量は O(n log n) です。