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

约定不等于承诺〃 2022-12-07 12:17 114阅读 0赞

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

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

**示例 1:**

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

**示例 2:**

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

**示例 3:**

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

解法1:

class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            max_len = 0
            max_list = []
    
            for item in s:
                max_list.append(item)
                if item in max_list[:-1]:
                    index = max_list.index(item)  # 寻找重复的 第一个值 的 索引；
                    max_list = max_list[index+1:]
                max_len = max(len(max_list), max_len)
            # 无法找出 最长子序列 吗
            return max_len

解法2: 84ms

class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            max_len = 0
            max_list = []
            for item in s:
                if item in max_list:
                    index = max_list.index(item)
                    max_list = max_list[index+1:] + [item]
                else:
                    max_list.append(item)
                max_len = max(len(max_list), max_len)
            return max_len

[Offer 48.]: https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/