JavaScriptで文字列をエンコードしてサイズを縮小する方法

問題

文字列 str を唯一の引数として受け取るJavaScript関数を作成します。この関数の役割は、入力文字列を特定のルールに従ってエンコードし、そのサイズを元の文字列と比較することです。そして、より小さいサイズとなった方の文字列を返します。

エンコードのルール

• n[s] — 角括弧内の文字列 s が、正確に n 回繰り返されることを表します。

たとえば、「ddd」は「3[d]」とエンコードできます。しかし「3[d]」の長さは4文字である一方、「ddd」はわずか3文字です。このように、エンコードするとかえってサイズが大きくなるケースでは、元の文字列「ddd」をそのまま返すのが正しい動作となります。

入力例

const str = 'aabcaabcd';

期待される出力

const output = '2[aabc]d';

解決アプローチ： 区間DP(動的計画法)

この問題は、各部分文字列の最適なエンコード結果を段階的に求めていく区間DPで効率的に解けます。dp[i][j] には、部分文字列 s.substring(i, j + 1) の最も短くなるエンコード結果を格納していきます。

1. まず、すべての部分文字列について「元の文字列そのもの」を初期候補とします。

2. 分割点 k を順にずらしながら、左側 dp[i][k] と右側 dp[k + 1][j] のエンコード結果を連結し、現在の候補より短ければ更新します。

3. さらに、その部分文字列が同じパターンの繰り返しになっていないかを調べます((sub + sub).indexOf(sub, 1) で最小の繰り返し単位を検出)。繰り返しが見つかれば「繰り返し回数[パターン]」の形式に圧縮し、短くなる場合のみ採用します。

これにより、入れ子になった繰り返し構造(例： 2[aabc]d)も正しく処理でき、全体として最短のエンコード結果が得られます。

実装コード

const str = 'aabcaabcd';
function encode(s) {
    const { length } = s;
    const dp = Array(length).fill([]);
    dp.forEach((el, ind) => {
        dp[ind] = Array(length).fill(null);
    });
    for(let l = 1; l <= length; l++){
        for(let i = 0; i + l <= length; i++){
            let j = i + l - 1;
            dp[i][j] = s.substring(i, j + 1);
            for (let k = i; k < j ; k ++) {
                let acc = dp[i][k] + dp[k + 1][j];
                if (acc.length < dp[i][j].length) {
                    dp[i][j] = acc;
                }
            }
            let sub = s.substring(i, j + 1);
            let double = sub + sub;
            let cut = double.indexOf(sub, 1);
            if (cut != -1 && cut < sub.length) {
                let acc = sub.length / cut + "[" + dp[i][i + cut - 1] +"]";
                if (acc.length < dp[i][j].length) {
                    dp[i][j] = acc;
                }
            }
        }
    }
    let res = dp[0][dp.length - 1];
    return res;
}
console.log(encode(str));

出力

コンソールには次の結果が出力されます。

2[aabc]d

この実装の計算量は区間の組み合わせ O(n²) × 分割点の走査 O(n) で、全体として約 O(n³) です。文字列がそれほど長くない場合に、常に理論上の最短エンコードを保証できるのが大きな特徴です。