题目解析

题目

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

示例分析

• 示例 1: 输入 "abcabcbb"，最长无重复字符子串是 "abc"，长度为 3。
• 示例 2: 输入 "bbbbb"，最长无重复字符子串是 "b"，长度为 1。
• 示例 3: 输入 "pwwkew"，最长无重复字符子串是 "wke"，长度为 3。注意 "pwke" 是一个子序列而非子串。

提示

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

解题思路

1. 滑动窗口法：使用滑动窗口遍历字符串，窗口内无重复字符时扩大窗口，有重复时缩小窗口。
2. 哈希表记录：利用哈希表存储字符及其索引，以快速判断字符是否重复以及定位重复字符的位置。
3. 双指针：维护窗口的左右指针，左指针指向子串开始位置，右指针遍历字符串。

代码实现

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 创建一个字典来存储字符和它们的索引
        char_index = {}
        max_length = 0
        start = 0

        for end in range(len(s)):
            if s[end] in char_index and char_index[s[end]] >= start:
                # 如果字符在窗口中且重复出现，更新窗口的起始位置
                start = char_index[s[end]] + 1
            char_index[s[end]] = end
            max_length = max(max_length, end - start + 1)

        return max_length

使用方法

调用 lengthOfLongestSubstring 函数，并传入字符串参数。

输出结果

函数将返回无重复字符的最长子串长度。

举例

print(length_of_longest_substring("abcabcbb"))  # 输出: 3
print(length_of_longest_substring("bbbbb"))  # 输出: 1
print(length_of_longest_substring("pwwkew"))  # 输出: 3

总结

这道题主要考察对滑动窗口算法的理解和应用。通过有效使用哈希表和双指针技巧，能够有效地解决问题，并且保证了代码的执行效率。

题目链接

https://leetcode.cn/problems/longest-substring-without-repeating-characters/