03、无重复字符的最长子串

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

哈喽，大家好，我是厨子，今天给大家分享一道经典题目，无重复字符的最长子串

题目

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

示例 1:

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

示例 2:

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

示例 3:

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

约束条件:

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

很简单，我们看到无重复，第一印象就能想到使用 set 来解决这个问题

解题思路

这是一道经典的滑动窗口问题

维护一个滑动窗口，窗口内的字符都是不重复的。当遇到重复字符时，收缩窗口左边界，直到窗口内没有重复字符为止。

知道了思想，我们来看一下应该如何设置吧

以字符串 "abcabcbb" 为例：

图解

暂时无法在飞书文档外展示此内容

代码实现

滑动窗口 + set

#include <unordered_map>
#include <string>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 哈希表记录字符最后出现的位置
        unordered_map<char, int> charIndex;
        int maxLen = 0;
        int left = 0;  // 窗口左边界

        for (int right = 0; right < s.size(); ++right) {
            char currChar = s[right];
            // 如果当前字符已在窗口中，移动左边界到该字符上次出现位置的右侧
            if (charIndex.find(currChar) != charIndex.end() && charIndex[currChar] >= left) {
                left = charIndex[currChar] + 1;
            }

            // 更新当前字符的最后出现位置
            charIndex[currChar] = right;

            // 更新最大长度（当前窗口长度为 right - left + 1）
            maxLen = max(maxLen, right - left + 1);
        }

        return maxLen;
    }
};

时间复杂度: O(n)，其中 n 是字符串长度

空间复杂度: O(min(m, n))，其中 m 是字符集大小

滑动窗口 + map

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> charIndex;
        int maxLen = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            if (charIndex.count(s[right]) && charIndex[s[right]] >= left) {
                left = charIndex[s[right]] + 1;
            }

            charIndex[s[right]] = right;
            maxLen = max(maxLen, right - left + 1);
        }

        return maxLen;
    }
};

两种方式的思路一致