重複なし最長部分文字列
窓の大きさが、先に決まらない
同じ文字が二度出てこない、連続した部分の最長を知りたい。abcabcbb なら abc の 3 文字、bbbbb なら b の 1 文字が答えです。
前の回は窓の大きさが先に与えられていました。今回は、その大きさこそが求めたいものです。
大きさが分からないなら全部試せばよい、と考えると行き詰まります。連続した部分の取り方は、始まりと終わりの組み合わせなので文字数の 2 乗ほどあり、その 1 本ずつについて重複の有無を調べれば、さらに文字数ぶんの手間がかかります。100 文字で 100 万回。決められないものを固定するのではなく、伸び縮みする窓にします。
伸ばせるだけ伸ばして、ぶつかったら左を捨てる
右端を 1 つずつ進め、窓の中身を増やしていきます。新しく入れようとした文字がすでに窓の中にあったら、その重複が消えるまで左端を右へ寄せます。abca で追ってみます。
aを入れる。窓はabを入れる。窓はabcを入れる。窓はabc。ここまでの最長は 3aを入れたい。窓の中にすでにaがある。左端のaを捨てて窓をbcにしてから、aを入れてbca
最後の窓も 3 文字なので、答えは 3 のままです。捨てるのは常に左端からで、右端は決して戻りません。だから「いま窓の中にいる文字」さえ分かっていれば、その場で判断がつきます。
縮めるのは 1 回とは限りません。abba で 3 文字目の b を入れようとすると、窓は ab から b、空へと縮み、そこでようやく b が入ります。捨てたい文字が窓の奥にいるほど、左端は多く進みます。だから「1 つ寄せる」ではなく「重複が消えるまで寄せる」と考えてください。
逆に、左端を戻したくなる場面はありません。窓を縮めたあとに、いったん捨てた文字がまた使えるようになることはないからです。
内側にループがあっても、全体は文字数ぶん
左を寄せる作業がループになるので、見た目は二重ループです。ところが左端は右へしか動かず、文字列の長さを超えて進むことはできません。全部の回を合計しても、左端の移動は文字数ぶんが上限です。右端も同じ。合わせても文字数の 2 倍で、2 乗にはなりません。
1 回あたりの最悪だけを見ると遅そうに見えても、全体で数えれば小さい。この見積もり方は、配列の自動拡張など、ほかの場面でも出てきます。
よくある間違い
窓の長さを 右端 - 左端 で計算することです。
Python
left, right = 1, 3
print(right - left) # 2
print(right - left + 1) # 3窓は左端と右端の両方を含むので、1 を足します。答えが常に 1 だけ小さくなるという、気づきにくい形で現れます。
演習で使う書き方
例は "xyxz" です。三文字目の x の直前には x と y があり、左の x を外してから新しい x を入れると窓は yx。その後 z を入れると yxz です。集合は set() で作り、in で所属確認、add で追加、remove で削除します。重複を消すループと最大長の比較を書きます。
要件
- 重複がなくなるまで左端を動かし、長さを比較を自分で実装する
- 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える