C++で文字列を最短の長さにエンコードするアルゴリズム(区間DP)

問題概要

空でない文字列が与えられます。この文字列を、エンコード後の長さが最小になるようにエンコードすることを考えましょう。

エンコードの規則は k[encoded_string] という形式です。これは、角括弧内の encoded_string がちょうど k 回繰り返されることを意味します。ただし、以下の条件があります。

• k は正の整数であること
• encoded_string は空であってはならず、余分な空白も含めない
• 入力文字列には小文字の英字のみが含まれると仮定できる
• エンコードしても文字列が短くならない場合は、エンコードを行わない

例えば、入力が "aaaaa" の場合、出力は "5[a]" となります。"5[a]" は "aaaaa" よりも1文字短いためです。

解き方：区間DPによるアプローチ

この問題は区間DP(動的計画法)で効率的に解けます。dp[i][j] には、部分文字列 s[i..j] に対する最短のエンコード結果を格納します。

手順1:collapse関数の定義

まず、部分文字列の周期的な繰り返しパターンを検出して圧縮する collapse() 関数を定義します。引数は s、i、j です。

• temp := s のインデックス i から j までの部分文字列
• x := temp を2回連結した文字列(temp + temp)
• pos := x 内で temp が出現する最初の位置(先頭の1文字をスキップして検索)
• pos >= temp のサイズの場合 → 周期パターンがないので temp をそのまま返す
• それ以外の場合 → to_string(temp.size() / pos) + "[" + dp[i][i+pos-1] + "]" を返す

ここでのポイントは、「文字列を自分自身と連結したものの中で、1文字目以降に自分自身が再び現れる位置」がそのまま最小周期の長さになるという性質を利用している点です。これにより、繰り返しパターンを効率よく検出できます。

手順2:encode関数の定義

次に、メインとなる encode() 関数を定義します。引数は s です。

1. n := s のサイズとし、dp を n × n の2次元配列として初期化する
2. 区間の長さ l を 1 から n まで順に処理する
3. i = 0、j = l - 1 から始め、j < n の間、i と j を1ずつ増やしながら繰り返す:
   • dp[i][j] := s のインデックス i から j までの部分文字列で初期化
   • 分割点 k を i から j - 1 まで動かしながら、temp := dp[i][k] + dp[k+1][j] を計算し、temp のサイズが dp[i][j] より小さければ更新する
   • rep := collapse(s, i, j) を計算し、そのサイズが dp[i][j] 以下なら dp[i][j] を rep で更新する
4. 最後に dp[0][n-1](文字列全体の最適なエンコード結果)を返す

このように、短い区間から順に最適解を求め、それを再利用しながら長い区間の答えを構築していくのが区間DPの基本的な流れです。

実装例(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<vector<string>> dp;
    string collapse(string &s, int i, int j) {
        string temp = s.substr(i, j - i + 1);
        string x = temp + temp;
        auto pos = x.find(temp, 1);
        if (pos >= temp.size())
            return temp;
        return to_string((temp.size() / pos)) + "[" + dp[i][i + pos - 1] + "]";
    }
    string encode(string s) {
        int n = s.size();
        dp = vector<vector<string>>(n, vector<string>(n, ""));
        for (int l = 1; l <= n; l++) {
            for (int i = 0, j = l - 1; j < n; i++, j++) {
                dp[i][j] = s.substr(i, j - i + 1);
                for (int k = i; k < j; k++) {
                    string temp = dp[i][k] + dp[k + 1][j];
                    if (temp.size() < dp[i][j].size()) {
                        dp[i][j] = temp;
                    }
                }
                string rep = collapse(s, i, j);
                if (rep.size() <= dp[i][j].size()) {
                    dp[i][j] = rep;
                }
            }
        }
        return dp[0][n - 1];
    }
};
main() {
    Solution ob;
    cout << (ob.encode("bbbbbbbbbb"));
}

入力

"bbbbbbbbbb"

出力

"10[b]"

まとめ

本アルゴリズムでは、区間DPによって各部分文字列の最短エンコードを段階的に求め、collapse() による周期性検出を組み合わせることで、"bbbbbbbbbb" → "10[b]" のような繰り返しパターンの圧縮にも柔軟に対応できます。時間計算量は区間の数 O(n²)、分割点 O(n)、文字列操作 O(n) を考慮すると最悪 O(n⁴)、空間計算量は各区間の結果を文字列として保持するため O(n³) となります。