LeetCode-Book/python/sfo_48_the_longest_substring_without_repeated_characters_s1.py at main · github-interview/LeetCode-Book

Repository navigation

'''

File: sfo_48_the_longest_substring_without_repeated_characters_s1.py

Created Time: 2021-12-09

Author: Krahets (krahets@163.com)

'''

from include import *

# ===== Solution Code =====

class Solution:

def lengthOfLongestSubstring(self, s: str) -> int:

dic = {}

res = tmp = 0

for j in range(len(s)):

i = dic.get(s[j], -1) # 获取索引 i

dic[s[j]] = j # 更新哈希表

tmp = tmp + 1 if tmp < j - i else j - i # dp[j - 1] -> dp[j]

res = max(res, tmp) # max(dp[j - 1], dp[j])

return res

# ======= Test Case =======

s = "abcabcbb"

# ====== Driver Code ======

slt = Solution()

res = slt.lengthOfLongestSubstring(s)

print(res)