《剑指Offer(第二版)》面试题48. 最长不含重复字符的子字符串

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

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

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

示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
 
提示:
s.length = 40000
# 相对于2D BP(O(N^2),O(1)), 使用hashmap保留字符的下一位置, O(N), O(N)

class Solution:
    def lengthOfLongestSubstring(self, s: str) - int:
        head = 0
        tail = 0
        res = 0
        dicts = {}# 记录字符的下一个位置
        while tail  len(s):
            if s[tail] in dicts:
                head = max(head, dicts[s[tail]])
            dicts[s[tail]] = tail+1
            res = max(res, tail-head+1)
            tail += 1
        return res

 

最新回复(0)
/jishu_2FlnrsjI8dD_2BWHJxl2B7JaG_2BMB5nBQxbv5RF_2F143yiYc_3D4858764
8 简首页