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

题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

题目链接

无重复字符的最长子串

要找出字符串 s 中不含有重复字符的最长子串的长度，可以使用滑动窗口技术。滑动窗口是一种常用的算法技巧，适用于解决这类问题，因为它可以在一次遍历中高效地找到最优解。

解题思路

1. 初始化变量：

   • left 和 right 两个指针，分别表示滑动窗口的左右边界。
   • max_length 用于记录最长子串的长度。
   • char_set 用于存储当前窗口内的字符，确保窗口内没有重复字符。

2. 滑动窗口：

   • 使用 right 指针从左到右遍历字符串。
   • 如果 right 指针指向的字符不在 char_set 中，将其添加到 char_set 中，并更新 max_length。
   • 如果 right 指针指向的字符已经在 char_set 中，说明出现了重复字符，需要移动 left 指针，直到窗口内不再包含重复字符。

3. 更新结果：

   • 每次移动 right 指针时，更新 max_length，确保记录最长的无重复字符子串的长度。

Python 实现

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 初始化变量
        left = 0
        max_length = 0
        char_set = set()
        # 滑动窗口
        for right in range(len(s)):
            # 如果当前字符不在集合中，添加到集合
            if s[right] not in char_set:
                char_set.add(s[right])
                max_length = max(max_length, right - left + 1)
            else:
                # 如果当前字符已经在集合中，移动左指针
                while s[right] in char_set:
                    char_set.remove(s[left])
                    left += 1
                char_set.add(s[right])
        return max_length

详细解释

1. 初始化变量：

   • left = 0：左指针初始位置为0。
   • max_length = 0：初始最长子串长度为0。
   • char_set = set()：初始化一个集合，用于存储当前窗口内的字符。

2. 滑动窗口：

   • for right in range(len(s))：右指针从0到字符串的最后一个位置遍历。
   • if s[right] not in char_set：如果当前字符不在集合中，将其添加到集合中，并更新 max_length。
   • else：如果当前字符已经在集合中，说明出现了重复字符，需要移动 left 指针，直到窗口内不再包含重复字符。
     • while s[right] in char_set：移动 left 指针，直到 s[right] 不在集合中。
     • char_set.remove(s[left])：从集合中移除 left 指针指向的字符。
     • left += 1：移动 left 指针。
   • char_set.add(s[right])：将当前字符添加到集合中。

3. 返回结果：

   • return max_length：返回最长无重复字符子串的长度。

通过这种方法，我们可以在一次遍历中找到最长的无重复字符子串，时间复杂度为 (O(n))，空间复杂度为 (O(min(n, m)))，其中 (n) 是字符串的长度，(m) 是字符集的大小。

原文地址：https://blog.csdn.net/sysu63/article/details/143906022

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！