JavaScriptで「全ての文字がn回以上出現する最長部分文字列」の長さを求める方法

問題の概要

本記事では、JavaScriptで以下のような関数を実装する方法を解説します。この関数は、第1引数として文字列を、第2引数として正整数 n を受け取ります。

与えられる文字列には、同じ文字が繰り返し含まれている可能性があります。関数の目的は、元の文字列から「すべての文字が少なくとも n 回出現している」部分文字列のうち最も長いものを見つけ出し、その長さを返すことです。

例えば、次のような入力を考えてみましょう。

const str = 'kdkddj';
const num = 2;

この場合、期待される出力は次のようになります。

const output = 5;

理由は簡単です。条件を満たす最長の部分文字列は「kdkdd」であり、この中で文字 k は2回、文字 d は3回出現しています。つまり、どちらの文字も2回（= n 回）以上現れているため、条件を満たすのです。末尾の j は1回しか出現しないため除外されます。

解決のアプローチ

この問題は、再帰的な分割統治法を使うことで効率的に解くことができます。基本的な考え方は次の通りです。

1. 文字列内の各文字の出現回数をハッシュマップでカウントする
2. 最も出現回数の少ない文字（最小頻度文字）を特定する
3. その最小頻度文字が n 回以上出現しているなら、文字列全体が条件を満たすため、その長さをそのまま返す
4. n 回未満であれば、その文字を区切りとして文字列を分割し、得られた各部分文字列に対して再帰的に同じ処理を適用する

この手法により、条件を満たせない文字を境に文字列を切り分けていくことで、無駄な探索を省きながら答えを絞り込めます。

コード例

以下が実際の実装コードです。

const str = 'kdkddj';
const num = 2;

const longestSubstring = (str = '', num) => {
    // 文字列の長さが n 未満なら条件を満たすことはできない
    if(str.length < num){
        return 0;
    };

    // 各文字の出現回数をカウント
    const map = {};
    for(let char of str) {
        if(char in map){
            map[char] += 1;
        }else{
            map[char] = 1;
        }
    }

    // 最も出現回数の少ない文字を取得
    const minChar = Object.keys(map).reduce((minKey, key) => map[key] < map[minKey] ? key : minKey);

    // 最小頻度文字が n 回以上なら全体が条件を満たす
    if(map[minChar] >= num){
        return str.length;
    };

    // 最小頻度文字で分割し、長さ n 以上の部分だけを残す
    substrings = str.split(minChar).filter((subs) => subs.length >= num);

    // 有効な部分文字列がなければ 0 を返す
    if(substrings.length == 0){
        return 0;
    };

    // 各部分文字列に対して再帰的に処理し、最大値を求める
    let max = 0;
    for(ss of substrings) {
        max = Math.max(max, longestSubstring(ss, num));
    };
    return max;
};

console.log(longestSubstring(str, num));

実行結果

コンソールには以下のように出力されます。

5

コードのポイント

• 早期リターン： 文字列の長さ自体が n 未満の場合、どんな文字も n 回出現することはできないため、即座に 0 を返して無駄な計算を回避しています。
• 最小頻度文字への着目： 条件を満たす部分文字列に最小頻度文字が含まれるなら、それは n 回以上現れているということ。逆に n 回未満なら、その文字を含まない範囲だけで答えを探せばよい、という発想が核心です。
• 再帰による絞り込み： 分割後の各部分文字列に対して同じロジックを適用することで、最終的に条件を満たす最長の長さが自然に求まります。

このように、頻度分析と再帰的な分割を組み合わせることで、シンプルかつ効率的に「全文字が n 回以上出現する最長部分文字列」の長さを求めることができます。