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

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

【题目链接】

解题

1. 最长不含重复字符的子字符串（动态规划 / 双指针 + 哈希表，清晰图解）

思路

代码

class Solution:
    ### 1104 动态规划 + 哈希表 O(N)（64 ms，13.4 MB）
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic, res, tmp = {}, 0, 0                    # 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)                     # 更新最大值
        return res

    ### 1104 动态规划 + 线性查找 O(N2)（484 ms，13.6 MB）
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = tmp = 0                               # tmp表示前一时刻最长不含重复字符的子字符串的长度，初始化为0
        for j in range(len(s)):                     # 遍历字符串中每一个字符
            i = j - 1                               # 初始化下标i，将i初始化为j左边的值
            while i>=0 and s[i] != s[j]: i -= 1     # 从右往左更新i（逆序）
            tmp = tmp + 1 if tmp < j - i else j - i # dp[j - 1] -> dp[j]
            res = max(res, tmp)                     # 更新最大值
        return res

    ### 1104 动态规划 + 双指针 O(N)（68 ms，13.6 MB）
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic, res, i = {}, 0, -1       # 初始化左指针i为-1
        for j in range(len(s)):       # 遍历字符串中每一个字符
            if s[j] in dic:           # 检查当前字符是否在哈希表中
                i = max(dic[s[j]], i) # 若存在，则更新左指针i
            dic[s[j]] = j             # 更新哈希表
            res = max(res, j - i)     # 更新最大值
        return res