重複なし最長部分文字列

窓の大きさが、先に決まらない

同じ文字が二度出てこない、連続した部分の最長を知りたい。abcabcbb なら abc の 3 文字、bbbbb なら b の 1 文字が答えです。

前の回は窓の大きさが先に与えられていました。今回は、その大きさこそが求めたいものです。

大きさが分からないなら全部試せばよい、と考えると行き詰まります。連続した部分の取り方は、始まりと終わりの組み合わせなので文字数の 2 乗ほどあり、その 1 本ずつについて重複の有無を調べれば、さらに文字数ぶんの手間がかかります。100 文字で 100 万回。決められないものを固定するのではなく、伸び縮みする窓にします。

伸ばせるだけ伸ばして、ぶつかったら左を捨てる

右端を 1 つずつ進め、窓の中身を増やしていきます。新しく入れようとした文字がすでに窓の中にあったら、その重複が消えるまで左端を右へ寄せます。abca で追ってみます。

• a を入れる。窓は a
• b を入れる。窓は ab
• c を入れる。窓は abc。ここまでの最長は 3
• a を入れたい。窓の中にすでに a がある。左端の a を捨てて窓を bc にしてから、a を入れて bca

最後の窓も 3 文字なので、答えは 3 のままです。捨てるのは常に左端からで、右端は決して戻りません。だから「いま窓の中にいる文字」さえ分かっていれば、その場で判断がつきます。

縮めるのは 1 回とは限りません。abba で 4 文字目の a を入れようとすると、窓は ab と b を経て空になり、そこでようやく a が入ります。捨てたい文字が窓の奥にいるほど、左端は多く進みます。だから「1 つ寄せる」ではなく「重複が消えるまで寄せる」と考えてください。

逆に、左端を戻したくなる場面はありません。窓を縮めたあとに、いったん捨てた文字がまた使えるようになることはないからです。

内側にループがあっても、全体は文字数ぶん

左を寄せる作業がループになるので、見た目は二重ループです。ところが左端は右へしか動かず、文字列の長さを超えて進むことはできません。全部の回を合計しても、左端の移動は文字数ぶんが上限です。右端も同じ。合わせても文字数の 2 倍で、2 乗にはなりません。

1 回あたりの最悪だけを見ると遅そうに見えても、全体で数えれば小さい。この見積もり方は、配列の自動拡張など、ほかの場面でも出てきます。

よくある間違い

窓の長さを 右端 - 左端 で計算することです。

窓は左端と右端の両方を含むので、1 を足します。答えが常に 1 だけ小さくなるという、気づきにくい形で現れます。

1. 計算量は O(n) であること (可変長スライディングウィンドウ + set)
2. 戻り値は重複なし最長部分文字列の長さ (整数)
3. 1 文字以上の文字列を仮定して良い