問題
原文
Given a string
s, find the length of the longest substring without repeating characters.
Example 1:
Example 2:
Example 3:
Constraints:
0 <= s.length <= 5 * 104sconsists of English letters, digits, symbols and spaces.
内容
文字列sが与えられます。最大部分文字列を見つけてください。
例3： s = “pwwkew”
“wke”が最大部分文字列であり、その長さは3です。
“pwke”は各要素の場所を変えてしまっているのでだめなようです。
※正しくない可能性があります。
方針
前提
・2つのポインタを使う
・それぞれのポインタは文字列sにおける部分文字列の左端と右端を指すインデックス
※左右のインデックスの差が部分文字列の長さを表す
実装のイメージ
・文字列s内の各文字を全探索する
・各文字が初出現の要素である限り右のポインタを右に伸ばし続ける
・既出要素がある場合で、その既出要素が左右のポインタの外側にある場合は右のインデックスを右に伸ばし続ける
・既出要素がある場合で、その既出要素が左右のポインタの内側にある場合は、左ポインタを右ポインタの右隣りに変更する
イメージ ※赤が左、青が右ポインタ
まずは左右のポインタを広げていく
a b c b b c
a b c b b c
a b c b b c ※bは既出(2文字目)なので、左ポインタを移動
a b c b b c ※左ポインタを最初のbの右隣りにして再スタート
↑この操作を最後まで繰り返して左右のポインタの幅が最大だった時の値を返す。
解答
解答1：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: #出現済み要素をキー、そのインデックスを値として保持する辞書 seen = {} #文字列sの左側のポインタとして使うインデックス left = 0 #最大部分文字列の長さを保持する変数 output = 0 #文字列sを全探索。rightは文字列sの右側のポインタとして使うインデックスでもある for right in range(len(s)): #right番目の要素が初出現の場合 if s[right] not in seen: #現在のoutputの大きさと、left～rightまでの幅の大きさの内、大きい方をoutputに代入 output = max(output,right-left+1) #right番目の要素が既出の場合 else: #既出要素(right番目の要素)の出現場所(インデックス)が左側のポインタleftの場所(インデックス)より小さい場合 #つまり、left～rightの中に既出の要素がない場合 if seen[s[right]] < left: #現在のoutputの大きさと、left～rightまでの幅の大きさの内、大きい方をoutputに代入 output = max(output,right-left+1) #既出要素がleft～rightの中にある場合は、left(インデックス)を既出要素(right番目の要素)の右隣りに移動 else: left = seen[s[right]] + 1 #right番目の要素は、その要素をキー、その出現位置(インデックス)を値として辞書seenに代入 seen[s[right]] = right #outputを返す return output |
解答2
補足・参考・感想
参考
自分が後で見返して理解しやすいように、ツールを使って図解しつつ、記事に組み込めるようにしたい。
コメント