C++で最長のハッピーストリングを構築する方法

問題の概要

文字列の中に「aaa」「bbb」「ccc」のように同じ文字が3つ連続する部分文字列がひとつも含まれていないとき、その文字列をハッピーな文字列と呼びます。

ここで、3つの整数 a、b、c が与えられます。このとき、次の条件をすべて満たす文字列 s を返してください。

• s はハッピーな文字列であり、かつ可能な限り長いこと。
• s には文字 'a' が最大 a 個、'b' が最大 b 個、'c' が最大 c 個含まれること。
• s は 'a'、'b'、'c' の3種類の文字のみで構成されること。

条件を満たす文字列が存在しない場合は、空文字列を返します。

たとえば a = 1、b = 1、c = 7 が入力された場合、出力は「ccaccbcc」や「ccbccacc」のような文字列になります。条件を満たす限り、答えは複数存在し得る点に注意してください。

解法のアプローチ：優先度付きキューを使った貪欲法

この問題は、残り個数が最も多い文字から優先的に配置していく貪欲法（グリーディ法）で効率よく解くことができます。同じ文字が3連続しないように制御するため、優先度付きキュー（priority_queue）を活用します。手順は以下の通りです。

1. 文字種（a）、残り個数（cnt）、挿入順序（idx）を保持するデータ構造 Data を定義します。
2. cnt の値を優先度とする優先度付きキュー pq を用意します。
3. a が 0 以外なら Data('a', a, 0) を pq に挿入します。b、c についても同様に行います。
4. idx を 1、結果文字列 ret を空文字列として初期化します。
5. 以下の処理を繰り返します。
   • pq の先頭要素を取り出し、temp とします。
   • ret が空でなく、ret の末尾文字が temp.a と一致する場合は、pq が空ならループを抜けます。空でなければ temp を一時退避させ、次の先頭要素を取り出した後、退避させていた要素を pq に戻します。
   • 今回追加する文字数 val を決定します。pq が空でなく、temp.cnt − pq 先頭要素の cnt が 2 未満であれば val = 1、そうでなければ val = min(temp.cnt, 2) とします。
   • ret の末尾に temp.a を val 個連結します。
   • temp.cnt から val を減算します。pq が空になったらループを抜けます。
   • temp.idx に idx を設定し、temp.cnt が 0 より大きければ temp を pq に戻します。
   • idx を 1 増やします。
6. 最後に ret を返します。

ポイントは、直前に使った文字が再び先頭に来た場合に、あえて2番目に個数の多い文字を挟むことで「3連続」を回避している点です。また、他の文字との残数差が小さい場合は1文字ずつ追加することで、全体のバランスを保ちながら文字列を最大化できます。

C++での実装例

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

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

struct Data {
    char a;
    int cnt;
    int idx;
    Data(char c, int x, int k) {
        a = c;
        cnt = x;
        idx = k;
    }
};

struct Cmp {
    bool operator()(Data& a, Data& b) {
        return !(a.cnt > b.cnt);
    }
};

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        priority_queue<Data, vector<Data>, Cmp> pq;
        if (a)
            pq.push(Data('a', a, 0));
        if (b)
            pq.push(Data('b', b, 0));
        if (c)
            pq.push(Data('c', c, 0));
        int idx = 1;
        string ret = "";
        while (true) {
            Data temp = pq.top();
            pq.pop();
            if (ret.size() && ret.back() == temp.a) {
                if (pq.empty())
                    break;
                Data x = temp;
                temp = pq.top();
                pq.pop();
                pq.push(x);
            }
            int val = 0;
            if (!pq.empty() && temp.cnt - pq.top().cnt < 2) {
                val = 1;
            }
            else
                val = min(temp.cnt, 2);
            ret += string(val, temp.a);
            temp.cnt -= val;
            if (pq.empty())
                break;
            temp.idx = idx;
            if (temp.cnt > 0)
                pq.push(temp);
            idx++;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.longestDiverseString(1, 1, 7);
}

実行例

入力：

1, 1, 7

出力：

ccbccacc

出力は「c」が最大7個・「a」と「b」がそれぞれ1個という制約を満たし、どこにも3連続する文字が含まれていない、有効な最長ハッピーストリングです。

計算量

各ループで少なくとも1文字が結果に追加され、対応する文字の残数が減っていくため、ループは最大 a + b + c 回程度しか回りません。優先度付きキューには常に3要素以下しか入らないため、各操作は O(log 3) = O(1) とみなせます。したがって、全体の時間計算量は O(a + b + c)、空間計算量も結果文字列を除けば O(1) となります。