Python 版 LeetCode 刷题笔记 #3 无重复字符的最长子串

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # temp 用来作为保存未重复字符的子串字符列表
        temp =[]
        # 返回的结果默认有个 0 ，因为最终测试时也会出现对 "" 空字符串处理的情况
        result=[0]
        # 对字符串进行遍历
        for i,item in enumerate(s):
            # 以被遍历的该字符为起点，遍历其后的各字符以组成子串
            for j,body in enumerate(s[i:]):
                # 如果重复出现字符
                if body in temp:
                    # 将子串的长度保存到结果列表中
                    result.append(len(temp))
                    # 该子串可以被清空继续检测新的子串
                    temp=[]
                    # 通过 break 跳出对后续字符的遍历，开启新的 for i 的循环
                    break
                else:
                    # 如果没有出现重复字符，将新出现的字符添加到子串字符列表中
                    temp.append(body)
                # 如果一直到最后一位都没有出现重复字符，将最后子串长度记录到结果中
                if j==len(s[i:])-1:
                    result.append(len(temp))
                    temp=[]
        # 返回结果列表中的最大值
        return max(result)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:        
        # 存放子串长度的结果列表
        result = []
        # 存放子串字符的列表
        temp=[]
        # 对输入字符串进行遍历
        for item in s:
            # 如果字符重复
            if item in temp:
                # 将子串长度添加到结果列表中
                result.append(len(temp))
                # 记录目前子串的初始位置
                start_index = temp.index(item)
                # 将子串初始位置右移一位、剔除重复的第一位，重新赋值给子串
                temp=temp[start_index+1:]
            # 无论是否字符重复，将该字符添加到子串列表中（重复时上一步已经剔除了）
            temp.append(item)
        # 将最后的子串长度记录
        result.append(len(temp))
        # 返回最长的子串
        return max(result)