C++で同じ文字が距離k以上離れるように文字列を並べ替える方法

問題の概要

空でない文字列 s と整数 k が与えられたとき、同じ文字同士が互いに少なくとも距離 k 以上離れるように文字列を並べ替えることを考えます。入力の文字列はすべて小文字の英字で構成されているものとします。条件を満たす並べ替えが存在しない場合は、空文字列を返します。

たとえば、入力が s = "aabbcc"、k = 3 の場合、出力は "abcabc" のようになります。これは、どの文字も同じ文字が再び現れるまでに3文字以上の間隔が空いているためです。

解き方のアプローチ：優先度付きキューとスライディングウィンドウ

この問題は貪欲法（グリーディ法）で効率よく解くことができます。基本となる考え方は次のとおりです。

• 各文字の出現回数をカウントし、残り出現数が多い文字から優先的に配置する。

• 直近 k 文字分の履歴を両端キュー（deque）で管理し、まだ使い切っていない文字が k 文字の窓から外れたタイミングで優先度付きキューへ戻し、再利用できるようにする。

• 処理の最後に、出現回数がまだ残っている文字（配置しきれなかった文字）が deque に残っていれば、並べ替えは不可能と判断する。

アルゴリズムの手順

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

• 結果を格納する文字列 ret を空文字列として初期化します。

• マップ m を定義します。

• n := 文字列 s の長さとします。

• i := 0 として、i < n の間 i を1ずつ増やしながら次を繰り返します。

  • m[s[i]] の値を1増やします（出現回数のカウント）。

• 優先度付きキュー pq を定義します（出現回数の多いものほど先に取り出せる構造にします）。

• m 内の各キーと値のペア it に対して、次を行います。

  • temp := it のキーと値からなるペアを作成します。

  • temp を pq に挿入します。

  • イテレータ it を1つ進めます。

• 両端キュー dq を定義します。

• pq が空になるまで、次を繰り返します。

  • curr := pq の先頭要素を取得し、pq から削除します。

  • ret に curr.first（文字）を連結します。

  • curr.second（残り出現回数）を1減らします。

  • curr を dq の末尾に追加します。

  • dq のサイズが k 以上になった場合：

    • curr := dq の先頭要素を取得し、dq から削除します。

    • curr.second > 0 であれば、curr を pq に戻します。

• dq が空でない間、先頭要素の second が 0 である限り、先頭要素を削除し続けます。

• dq が空であれば ret を、そうでなければ空文字列を返します。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Comparator {
    bool operator()(pair<char, int> a, pair<char, int> b) {
        return !(a.second > b.second);
    }
};
class Solution {
public:
    string rearrangeString(string s, int k) {
        string ret = "";
        unordered_map<char, int> m;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            m[s[i]]++;
        }
        unordered_map<char, int>::iterator it = m.begin();
        priority_queue<pair<char, int>, vector<pair<char, int>>,
        Comparator> pq;
        while (it != m.end()) {
            pair<char, int> temp = {it->first, it->second};
            pq.push(temp);
            it++;
        }
        deque<pair<char, int>> dq;
        while (!pq.empty()) {
            pair<char, int> curr = pq.top();
            pq.pop();
            ret += curr.first;
            curr.second--;
            dq.push_back(curr);
            if (dq.size() >= k) {
                curr = dq.front();
                dq.pop_front();
                if (curr.second > 0)
                pq.push(curr);
            }
        }
        while (!dq.empty() && dq.front().second == 0)
            dq.pop_front();
        return dq.empty() ? ret : "";
    }
};
int main() {
    Solution ob;
    cout << (ob.rearrangeString("aabbcc", 3));
}

このコードでは、Comparator 構造体によって優先度付きキューの比較基準を定義し、出現回数の多い文字が常に先に選ばれるようにしています。これにより、文字列の後半で特定の文字が集中して配置されてしまう事態を防ぐことができます。

入力

"aabbcc", 3

出力

bacbac

出力は "bacbac" ですが、"abcabc" のように同じ文字が距離3以上離れていれば、どの並びでも正解として扱われます。

計算量の目安

時間計算量は O(n log n)、空間計算量は O(n) です（n は文字列の長さ）。各文字は最大で n 回キューに出入りし、優先度付きキューへの挿入・削除には1回あたり対数時間がかかるためです。