无重复字符的最长子串

1、题目

image-20231024215656387

2、题解

1 滑动窗口+哈希表

思路：

哈希表\(dic\)统计字符串\(s\)中每个字符最后出现的位置。

设置两个指针\(i、j\)，\(j\)指针遍历字符串，当遍历到重复字符时，\(i\)指针根据上轮的\(i\)和\(dic[s[j]]\)更新，保证区间\([i+1,j]\)中无重复字符且最大。

每轮的结果为上轮结果和本轮双指针区间长度中的最大值。

代码实现：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        res = 0
        i = -1
        for j in range(len(s)):
            if s[j] in dic:
                i=max(dic[s[j]], i)
            dic[s[j]] = j
            res = max(res, j-i)
        return res     

复杂度分析：

• 时间复杂度\(O(N)\) ： 其中 \(N\) 为字符串长度，动态规划需遍历计算 \(dp\)列表。
• 空间复杂度 \(O(1)\) ： 字符的 ASCII 码范围为$ 0 ~ 127$ ，哈希表 \(dic\) 最多使用 \(O(128)=O(1)\) 大小的额外空间。

2 动态规划+哈希表

思路：

image-20231024222023682

image-20231024222111824

代码实现：

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