JavaScriptで循環するアルファベット文字列に含まれる一意な部分文字列を数える方法

問題概要

文字列 "abcdefghijklmnopqrstuvwxyz" を無限に繰り返してできる循環文字列 S を考えてみましょう。このとき、S は次のような形になります。

"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

今回実装するのは、引数として文字列 str を1つだけ受け取る JavaScript 関数です。この関数は以下の処理を行います。

• str の空でない部分文字列のうち、S に含まれるものをすべて洗い出す。

• S 内に存在する str の異なる非空部分文字列の個数を最終的な結果として返す。

たとえば、関数への入力が次のようだったとします。

const str = "zab";

この場合の出力は次の通りです。

const output = 6;

出力の解説

文字列 "zab" の部分文字列には "z"、"a"、"b"、"za"、"ab"、"zab" の6つがあり、これらはいずれも文字列 S に含まれています。そのため、答えは 6 となります。

解法のポイント

この問題は、動的計画法(DP)を使うことで効率的に解けます。長さ26の dp 配列を用意し、dp[i] には「文字 ('a' + i) で終わる連続した部分文字列の最大長」を記録します。隣り合う2文字が 'a' → 'b' のように連続しているか、あるいは 'z' → 'a' への折り返しかどうかを、文字コードの差分が 1 または -25 であるかで判定するのがポイントです。ある文字で終わる長さ n の部分文字列が存在すれば、それより短い部分文字列はすべて自動的にカバーされるため、Math.max で更新しながら重複を排除できます。最終的に dp 配列の全要素を合計した値が答えになります。

コード例

この処理を実装したコードは以下の通りです。

const str = "zab";
const allSubstrings = (str = '') => {
    const dp = new Array(26).fill(0);
    dp[str.charCodeAt(0) - 97] = 1;
    maxCount = 1;
    for (let i = 1; i < str.length; i++) {
        if ((str.charCodeAt(i) - str.charCodeAt(i - 1) == 1) || (str.charCodeAt(i) - str.charCodeAt(i - 1) == -25)) {
            maxCount++;
        } else {
            maxCount = 1;
        }
        dp[str.charCodeAt(i) - 97] = Math.max(dp[str.charCodeAt(i) - 97], maxCount);
    }
    return dp.reduce((item, val) => {
        return val + item;
    })
};
console.log(allSubstrings(str));

出力結果

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

6