无重复字符的最长字串

题解思路

本题要求找到字符串中最长的无重复字符子串的长度，可以使用 滑动窗口（Sliding Window） + 哈希集合（HashSet） 进行优化。

1. 定义双指针（左右指针）

   • left 指向当前窗口的起点。
   • right 指向当前窗口的终点，不断向右扩展。

2. 使用哈希集合存储当前窗口内的字符

   • 当 right 指向的字符未在窗口中出现时，加入集合，并更新最大长度 max_length。
   • 当 right 指向的字符已在窗口中出现时，移动 left 指针，直到 right 指向的字符不再重复。

3. 重复上述步骤，直到 right 遍历完整个字符串。

复杂度分析

• 时间复杂度：O(n)，right 指针遍历 n 个字符，每个字符最多被 left 指针访问一次。
• 空间复杂度：O(min(n, |Σ|))，Σ 是字符集大小，使用集合存储窗口中的字符。

代码

注意题目输入里有空格

Python 代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 哈希集合存储窗口内的字符
        char_set = set()
        left = 0  # 窗口左指针
        max_length = 0  # 记录最长子串的长度

        for right in range(len(s)):  # 右指针遍历字符串
            while s[right] in char_set:  # 如果字符重复
                char_set.remove(s[left])  # 移除左指针对应的字符
                left += 1  # 左指针右移
            
            char_set.add(s[right])  # 将新字符加入集合
            max_length = max(max_length, right - left + 1)  # 更新最大长度
        
        return max_length

# 示例测试
if __name__ == "__main__":
    s = input()
    solution = Solution()
    print(solution.lengthOfLongestSubstring(s))

Java 代码

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            HashSet<Character> charSet = new HashSet<>(); // 哈希集合存储窗口内的字符
            int left = 0; // 窗口左指针
            int maxLength = 0; // 记录最长子串的长度

            for (int right = 0; right < s.length(); right++) { // 右指针遍历字符串
                while (charSet.contains(s.charAt(right))) { // 如果字符重复
                    charSet.remove(s.charAt(left)); // 移除左指针对应的字符
                    left++; // 左指针右移
                }
                charSet.add(s.charAt(right)); // 将新字符加入集合
                maxLength = Math.max(maxLength, right - left + 1); // 更新最大长度
            }

            return maxLength;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        Main main = new Main();
        Solution solution = main.new Solution();
        System.out.println(solution.lengthOfLongestSubstring(s));
        scanner.close();
    }
}

C++ 代码

#include <iostream>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> charSet; // 哈希集合存储窗口内的字符
        int left = 0; // 窗口左指针
        int maxLength = 0; // 记录最长子串的长度

        for (int right = 0; right < s.length(); right++) { // 右指针遍历字符串
            while (charSet.find(s[right]) != charSet.end()) { // 如果字符重复
                charSet.erase(s[left]); // 移除左指针对应的字符
                left++; // 左指针右移
            }
            charSet.insert(s[right]); // 将新字符加入集合
            maxLength = max(maxLength, right - left + 1); // 更新最大长度
        }

        return maxLength;
    }
};

int main() {
    string s;
    getline(cin, s); // 读取输入
    Solution solution;
    cout << solution.lengthOfLongestSubstring(s) << endl;
    return 0;
}

题目内容

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

输入描述

一行字符串$s$

输出描述

一个整数，表示答案。

样例1

输入

abcabcbb

输出

3

说明

因为无重复字符的最长子串是 "$abc$"，所以其长度为 $3$。

样例2

输入

bbbbb

输出

1

说明

因为无重复字符的最长子串是 "$b$"，所以其长度为$1$。

样例3

输入

pwwkew

输出

3

说明

因为无重复字符的最长子串是 "$wke$"，所以其长度为$3$。

请注意，你的答案必须是 子串 的长度，"$pwke$" 是一个子序列，不是子串。

提示

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