Longest Substring Without Repeating Characters
文字列 s が与えられます。同じ文字が2回以上現れない、隣り合う文字の連続部分である最長の部分文字列を見つけ、その長さを返してください。
大文字と小文字は異なる文字として扱うため、a と A は重複ではありません。
関数
- sstring
- 検索する文字列
- 戻り値integer
- 文字が重複しない最長部分文字列の長さ
制約
1 ≤ s.length ≤ 5 × 104sには英字（小文字と大文字）と数字だけが含まれます。- 大文字と小文字は異なる文字です。
例
- 入力
- s = "coddycode"
- 出力
- 5
- 説明
ycodeには5つの異なる文字が含まれています。その前にdを加えると、dが2回含まれるdycodeになり、ほかに5文字以上の並びで文字の重複を避けられるものはありません。
- 入力
- s = "racecar"
- 出力
- 4
- 説明
raceとecarはどちらも異なる文字が4つあります。5文字の並びには、同じ文字が必ず2回含まれています。
- 入力
- s = "a1b2a3b"
- 出力
- 5
- 説明
- 数字も文字として数えるため、
1b2a3には異なる文字が5つあります。長さ6のどちらの連続部分にも、2つ目のaまたは2つ目のbが含まれています。
発展問題
もしsが英字や数字ではなく、任意のUnicode文字を保持できるとしたら、何を変更しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
部分文字列とは、文字列の連続した一部分です。そのため、同じ文字に二度出会わずに進める、最も長い範囲を探します。
左端と右端のあるウィンドウを保ちます。右側で1文字ずつ広げ、新しい文字がすでにウィンドウ内にある場合にのみ左端を移動します。
各文字が最後に出現したインデックスを保存します。新しい文字が左端以降に最後に出現していた場合は、左端をそのインデックスの1つ後ろに移動します。左端が後戻りすることはなく、答えはこれまでに得られた最も幅の広いウィンドウです。
解説
ウィンドウを維持します。重複する文字のない連続部分を両端で挟みます。右端は各文字を一度ずつ読み取り、左端は前方にのみ移動するため、1回の走査で、各終端について、そこで終わる重複のない最長の連続部分が見つかります。
すべての部分文字列を確認する
正しいが、最大のテストでは終わらない
考え方
すべての開始位置と終了位置を試し、各部分文字列の文字を集合に追加しながら、すでに集合にある文字が見つかるまでテストします。すべての候補がテストされるため、最長の有効な部分文字列を見逃すことはありません。
部分文字列は約 n²/2 個あり、n = 5 × 10^4 のとき 1.25 × 10^9 個です。また、1 回のテストで最大 n 文字を読み取ることがあるため、O(n³) です。ここでは、文字列に含まれる異なる文字は 62 種類だけなので、テストは最大 63 文字で終了しますが、それでも 10 億回を超えるテストが残ります。
アルゴリズム
bestを0に設定します。- 各開始インデックスについて、文字列の先頭から末尾まで、開始位置から各終了インデックスまでの範囲をループします。
- 部分文字列の文字を1文字ずつ空の集合に追加し、すでに集合に含まれている文字が見つかった時点で停止します。
- 文字が重複せず、部分文字列が
bestを上回る場合、その長さを保存します。 bestを返します。
def lengthOfLongestSubstring(s):
def has_no_repeat(start, end):
seen = set()
for k in range(start, end + 1):
if s[k] in seen:
return False
seen.add(s[k])
return True
best = 0
n = len(s)
for start in range(n):
for end in range(start, n):
if has_no_repeat(start, end):
best = max(best, end - start + 1)
return best
集合を使ったスライディングウィンドウ
考え方
abc に繰り返しがなければ、abcd を調べるために必要な質問は1つです。d は a、b、c の中にあるでしょうか？ウィンドウ内の文字の集合を使えば、一度に答えられます。
right を一度に1ステップずつ進めます。新しい文字が集合に含まれている場合は、その文字の前の出現がなくなるまで左側から文字を削除し、その文字を追加して長さを測ります。必要なときだけ文字を削除するので、それぞれの right について、ウィンドウはそこで終わる繰り返しのない最長の連続部分となり、最良の部分文字列はどこかで終わります。各文字は集合に1回入り、削除されるのは多くても1回です。O(n)。
アルゴリズム
- 空の集合から始め、
left = 0とbest = 0を設定します。 - すべてのインデックスを順に
rightで走査します。 s[right]が集合に含まれている間、s[left]を削除し、leftを1つ進めます。s[right]を集合に追加します。right - left + 1がbestを上回る場合、その値を保存します。bestを返します。
def lengthOfLongestSubstring(s):
in_window = set() # the characters between left and right
left = 0
best = 0
for right in range(len(s)):
# Shrink from the left until s[right] is no longer inside.
while s[right] in in_window:
in_window.remove(s[left])
left += 1
in_window.add(s[right])
best = max(best, right - left + 1)
return best
最後に確認されたインデックスまでジャンプするスライディングウィンドウ
考え方
left をどこに移動させるべきかは、もうわかっています。新しい文字の以前の出現位置の1つ先です。各文字の最後のインデックスを、マップまたは文字コードごとに1つの要素を持つ配列に保存すれば、left は一度の操作でそこに移動します。
そのインデックスが left 以上の場合にのみ移動します。それより前の出現位置はすでにウィンドウの外にあり、そこへ移動すると left が後ろに戻ってしまいます。各ステップでのウィンドウはセットを使う方法で作られるものと同じで、各文字に必要なのはルックアップ、比較、書き込みがそれぞれ1回ずつです。
アルゴリズム
- 文字から最終インデックスへの空のマップを作成し、
left = 0とbest = 0を設定します。 - すべてのインデックスを順に
rightで移動し、その位置の文字chを読み取ります。 chがleft以上の位置で最後に出現していた場合、leftをそのインデックスに 1 を足した値に設定します。rightをchの最終インデックスとして記録します。right - left + 1がbestを上回る場合、その値を保存します。bestを返します。
def lengthOfLongestSubstring(s):
last_seen = {}
start = 0
best = 0
for i, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= start:
start = last_seen[ch] + 1
last_seen[ch] = i
if i - start + 1 > best:
best = i - start + 1
return best
落とし穴と境界ケース
leftを後ろに動かす。abbaでは、最後のaに到達したとき、インデックス0にある先行するaはすでにウィンドウの外にあります。インデックス1に移動すると、2つ目のbがウィンドウに戻り、2ではなく3になります。- ウィンドウの長さを
right - leftとして数える。両端ともウィンドウに含まれるため、1を加えます。 - 最初に文字列を小文字に変換する。ここでは
aとAは異なる文字なので、aAの長さは2です。 - 文字が繰り返されたときだけ長さを測る。
zのように繰り返しのない文字列では、その処理が実行されず、答えは0になります。
よくある質問3
重複する文字を含まない最長部分文字列の時間計算量は何ですか？
スライディングウィンドウの実行時間は O(n) です。ここで n は文字列の長さです。右端は各文字を1回ずつ読み取り、左端は前方にのみ移動します。追加の空間計算量は O(k) です。ここで k は文字列に含められる異なる文字の数で、この場合は 62 です。
最後のインデックスにはハッシュマップと配列のどちらを使うべきですか？
どちらも時間計算量は O(n) です。ここでのように文字の種類が少数に固定されている場合、文字コードをインデックスとする配列を使えばハッシュ化を避けられ、より高速です。
部分文字列と部分列の違いは何ですか？
部分文字列とは、coddycodeの中のodeのように、隣り合う文字のまとまりです。部分列は、cdyのように文字を飛ばすことができます。この問題で求められているのは部分文字列なので、両端のあるウィンドウが機能します。
def lengthOfLongestSubstring(s):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "coddycode"
期待される出力
5