剑指 Offer 48. 最长不含重复字符的子字符串

剑指 Offer 48. 最长不含重复字符的子字符串

问题

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

分析

用哈希表更新字符的最新出现的位置；

用双指针记录当前最长字符串的长度；

左指针位置由以下两个值取最大得到：1. 当前字符上一个出现的位置；2. 上一个出现重复字符的位置；

复杂度：$T(n) = O(n); S(n) = O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        hash_table = {}
        length = len(s)
        res = 0
        loc_start = -1
        for i in range(length):
            if s[i] not in hash_table: hash_table[s[i]] = -1
            if loc_start < hash_table[s[i]]:
                cur = i - hash_table[s[i]]
                loc_start = hash_table[s[i]] # 更新左指针位置
            else:
                cur = i - loc_start
            if cur > res: res = cur 
            hash_table[s[i]] = i 
        return res