C++で長さnのすべてのハッピー文字列からk番目の辞書順文字列を求める方法

ハッピー文字列とは

「ハッピー文字列」とは、'a'、'b'、'c' の3種類の文字のみで構成され、かつ隣接する任意の2文字が異なる(s[i] != s[i + 1])という条件を満たす文字列のことです。つまり、同じ文字が連続して現れない文字列を指します。

問題の概要

2つの整数 n と k が与えられたとき、長さ n のすべてのハッピー文字列を辞書順に並べたリストを考えます。このリストの k 番目の文字列を求めてください。ただし、長さ n のハッピー文字列が k 個未満しか存在しない場合は、空文字列を返します。

例えば、n = 3、k = 9 とすると、出力は "cab" になります。長さ3のハッピー文字列は全部で12個存在し、["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"] となります。このうち9番目にあたるのが "cab" です。

解法のアプローチ

この問題は、深さ優先探索(DFS)による全列挙とソートを組み合わせて解くことができます。具体的には、以下の手順に従います。

• 結果を格納する配列 ret を定義します
• 関数 solve() を定義します。引数は文字列 s と整数 l(初期値は1)です
• l が目標の長さ x と等しい場合:
  • s を ret の末尾に追加します
  • 再帰を終了します
• i を 0 から 2 までループさせます:
  • s の末尾の文字が c[i] と異なる場合のみ、solve(s + c[i], l + 1) を再帰的に呼び出します

メインメソッドでは、以下の処理を行います。

• x に n を代入します
• n が 0 の場合は空文字列を返します
• solve("a")、solve("b")、solve("c") をそれぞれ呼び出し、すべてのハッピー文字列を生成します
• 配列 ret を辞書順にソートします
• k が ret のサイズより大きければ空文字列を、そうでなければ ret[k - 1] を返します

実装例

理解を深めるために、以下のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Cmp{
    bool operator()(string& a, string& b) {
        return !(a < b);
    }
};
char c[3] = {'a', 'b', 'c'};
class Solution {
public:
    vector<string> ret;
    int x;
    void solve(string s, int l = 1){
        if (l == x) {
            ret.push_back(s);
            return;
        }
        for (int i = 0; i < 3; i++) {
            if (s.back() != c[i]) {
                solve(s + c[i], l + 1);
            }
        }
    }
    string getHappyString(int n, int k){
        x = n;
        if (n == 0)
            return "";
        solve("a");
        solve("b");
        solve("c");
        sort(ret.begin(), ret.end());
        return k > ret.size() ? "" : ret[k - 1];
    }
};
main(){
    Solution ob;
    cout << (ob.getHappyString(3,9));
}

入力

3,9

出力

cab

補足:計算量について

長さ n のハッピー文字列の総数は 3 × 2^(n-1) 個になります。最初の文字は3通り選べ、以降の各文字は直前の文字以外の2通りから選ぶためです。したがって、事前にこの総数と k を比較すれば、生成処理を実行する前に答えが存在するかどうかを判定することも可能です。全列挙の計算量は O(2ⁿ) 程度であり、n が小さい範囲では十分に高速に動作します。