JavaScriptで文字列をできるだけ多くの部分に分割するアルゴリズム

文字列処理のアルゴリズム問題としてよく知られている「Partition Labels」をJavaScriptで解いてみましょう。この記事では、各文字が1つの部分にしか現れないように、文字列をできるだけ多くの部分へ分割する方法を解説します。

問題の定義

まず、文字列 str を引数として受け取るJavaScript関数を作成します。この関数の目的は、以下の条件を満たすように文字列を可能な限り多くの部分に分割することです。

• 各文字（英字）は、最大でも1つの部分にしか出現しない
• 戻り値は、各部分の長さを表す整数の配列

例を見てみましょう。

入力：

const str = "ababcbacadefegdehijhklij";

出力：

const output = [9, 7, 8];

出力の説明：

この場合、分割結果は "ababcbaca"、"defegde"、"hijhklij" の3つになります。それぞれの文字が1つの部分にのみ含まれているため、正しい分割です。

一方、"ababcbacadefegde"、"hijhklij" のように2つに分割するのは誤りです。なぜなら、同じ部分に複数の文字が重複して現れる可能性があり、さらに部分の数が少なくなってしまうからです。この問題では「できるだけ多くの部分」に分割することが求められます。

アプローチ：貪欲法と最後の出現位置

この問題を効率的に解く鍵は、各文字が最後に現れるインデックスを事前に記録しておくことです。手順は以下の通りです。

1. 1回目のループで、各文字が最後に登場する位置をマップ（連想配列）に記録する
2. 先頭から走査し、現在の部分に含まれるすべての文字の「最後の出現位置」の中で最も遠いものを区間の終点 end とする
3. 走査位置が end に達したら、その時点で1つの部分が確定し、その長さを結果に追加する
4. 次の部分の開始位置を end + 1 に更新し、文字列の末尾まで繰り返す

この貪欲法により、時間計算量 O(n)、空間計算量 O(1)（英小文字26種類分のマップのみ）で解くことができます。

実装コード例

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

const str = "ababcbacadefegdehijhklij";
const splitStrings = (str = '') => {
    const res = []
    const map = {}
    // 各文字の最後の出現位置を記録
    for (let i = 0; i < str.length; i++) {
        map[str[i]] = i
    }
    let start = 0
    while (start <= str.length - 1) {
        // 現在の部分の暫定的な終点
        let end = map[str[start]]
        // 区間内の文字について、より遠い最終出現位置があれば終点を拡張
        for (let i = start + 1; i < end; i++) {
            const currentEnd = map[str[i]]
            if (currentEnd > end) {
                end = currentEnd
            }
        }
        // 部分の長さを記録し、次の開始位置へ
        res.push(end - start + 1)
        start = end + 1
    }
    return res
};
console.log(splitStrings(str));

コードのポイント解説

• map の構築： ループで文字列を走査し、各文字キーに対して最後に出現したインデックスを上書き保存します。これにより O(1) での参照が可能になります。
• end の拡張： 内側の for ループは、現在確定候補となっている区間 [start, end) の中に含まれる文字を調べ、それらの文字がさらに後方に出現する場合は end を延長します。これにより、区間内の全文字が区間外に現れないことが保証されます。
• while ループ： start を end + 1 に進めることで、確定済みの部分をスキップし、次の独立した部分の探索に移ります。

実行結果

[ 9, 7, 8 ]

期待どおり、文字列 "ababcbacadefegdehijhklij" が長さ 9、7、8 の3つの部分に分割されました。

まとめ

このアルゴリズムは、各文字の最終出現位置を活用した貪欲法の好例です。「区間のマージ」と似た発想であり、インタビューでも頻出のパターンです。文字列だけでなく、配列の区間分割系の問題にも応用できる考え方なので、ぜひ理解しておきましょう。