JavaScriptで最大2種類の異なる文字を含む最長の文字列の長さを求める方法

問題の概要

JavaScriptで、文字列を引数として受け取る関数を作成します。この関数は、元の文字列から不要な文字を削除し、「最大でも2種類の異なる文字」だけで構成される最長の文字列を作り出します。そして最後に、その文字列の長さを返します。

なお、文字を削除しても残った文字の相対的な並び順は保たれます。そのため、この問題は厳密には連続した「部分文字列」ではなく、「部分列（subsequence）」を求める問題だと言えます。

たとえば、入力文字列が次の場合を考えてみましょう。

const str = 'kjeljsdl';

このとき、期待される出力は次のとおりです。

const output = 4;

理由は、「k」「e」「s」「d」を削除すると「j」「l」「j」「l」だけが残り、これが最大2種類の文字で構成できる最長の並び「jljl」（長さ4）となるためです。

解き方のポイント：出現回数を数えるだけ

一見すると複雑そうな問題ですが、実はとてもシンプルです。削除によって任意の位置の文字を取り除けるため、「残したい2種類の文字」を決めてしまえば、それらの文字は元の文字列に現れた回数ぶんすべて残すことができます。

つまり、答えは次の手順で求められます。

1. 文字列に含まれる各文字の出現回数を集計する。
2. 出現回数を多い順に並べ替える。
3. 文字が2種類以上ある場合は上位2文字の出現回数の合計を、1種類しかない場合はその出現回数を返す。

コード例

上記のアイデアを実装したコードがこちらです。

const str = 'kjeljsdl';

const longestSubstring = (str = '') => {
    // 空文字列の場合は 0 を返す
    if (!str) {
        return 0;
    }
    // 各文字の出現回数を集計する
    const freq = {};
    for (const ch of str) {
        freq[ch] = (freq[ch] || 0) + 1;
    }
    // 出現回数を多い順に並べ替える
    const counts = Object.values(freq).sort((a, b) => b - a);
    // 1種類ならその回数、2種類以上なら上位2つの合計を返す
    return counts.length === 1 ? counts[0] : counts[0] + counts[1];
};

console.log(longestSubstring(str));

出力

コンソールには次のように表示されます。

4

計算量について

文字の集計には文字列の長さ n に比例した O(n) の時間がかかり、並べ替えには文字の種類数 m に対して O(m log m) の時間がかかります。したがって全体の計算量は O(n + m log m) となります。扱う文字の種類が英小文字などに限られるケースでは m を定数とみなせるため、実質的に線形時間で高速に処理できます。