leetcode | 3.无重复字符的最长子串

3.无重复字符的最长子串

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

题目链接

思路

找出字符串中所有不包含重复字符的字串,返回长度最长的一个子串

代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """找出字符串中所有不包含重复字符的字串,返回长度最长的一个子串"""
        s_list = list(s)  # 将字符串转化为列表
        max_length = 0  # 最大字串长度

        # 找出以字符串中的每个字母开头的不包含重复字符的字串
        for i in range(0, len(s_list)):
            sub_str_list = []
            sub_str_list.append(s_list[i])
            for j in range(i + 1, len(s_list)):
                if s_list[j] not in sub_str_list:
                    sub_str_list.append(s_list[j])
                else:  # 遇到字串中已有的字符,则结束当前子串的寻找
                    break
            # print("sub_str_list:", sub_str_list)

            if len(sub_str_list) > max_length:
                max_length = len(sub_str_list)
                # print("max_length:", max_length)
                sub_str = ""
                for e in sub_str_list:
                    sub_str += e
                # print("sub_str:", sub_str)
                # print("long_sub_str:", sub_str)

        print("无重复字符的最长字串是{},长度为{}".format(sub_str, max_length))

        return max_length

    def lengthOfLongestSubstring1(self, s: str) -> int:
        # 哈希集合，记录每个字符是否出现过
        occ = set()
        n = len(s)
        # 右指针，初始值为-1，相当于我们在字符串的左边界的左侧，还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动一格，移动一个字符
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断地移动右指针
                occ.add(s[rk + 1])
                rk += 1
            # 第i到rk个字符是一个极长的无重复字符字串
            ans = max(ans, rk - i + 1)
        return ans


if __name__ == "__main__":
    s = "pwwkew"
    slt = Solution()
    len_long_sub_str = slt.lengthOfLongestSubstring1(s)
    print(len_long_sub_str)