LeetCode 3. Longest Substring Without Repeating Characters
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
tmp_max = 0
tmp_head = 0
if len(s) == 0:
return 0
dic = dict()
for i in range(len(s)):
if s[i] not in dic:
dic[s[i]] = i
else:
if dic[s[i]] >= tmp_head:
tmp_max = max(tmp_max, i - tmp_head)
tmp_head = max(tmp_head, dic[s[i]] + 1)
dic[s[i]] = i
tmp_max = max(tmp_max, len(s) - tmp_head)
return tmp_max
tmp_max : 条件を満たす最大の文字数
tmp_head: 現在の文字列の先頭
dic: ある文字が最後に現れた場所を表す
方針
文字s[i]が文字列sの中で初めて現れる文字だったら、現在チェックしている「同じ文字がリピートされない文字列」の文字数が増えるだけなので、そのまま辞書に登録する
文字s[i]が文字列sにすでに現れたことがある文字のとき
・すでに現れている文字がtmp_headより後に現れているなら、tmp_head、tmp_maxを更新
・tmp_headより前に現れているなら、今見ている文字列に付け加えても問題ないので、dicの値を更新して終わり