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

题目

给定一个字符串 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 由英文字母、数字、符号和空格组成

解答

思路

以 abcabcbb 为例，我们首先从 abc 开始，当遇到下一个元素 a 时，发现遇到了重复元素，于是我们就把 左端点右移，由于我们每次都是把一个 无重复元素的子串 后面接入新的字符，那么 重复只可能来自这个元素，于是左端点右移直到去除掉这个元素即可。

由于我们这样操作相当于依次枚举 以右端点为终点 的连续子串，因此不会漏掉情况。

使用哈希表来记录子串中的元素，以及查询新加入的元素是否在子串中，因此：

• 时间复杂度为 $O(n)$
• 空间复杂度为 $O(128)$

代码

C++ 代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        int left = 0;
        int right = 0;

        unordered_set<char> st;

        for (; right < s.size(); right ++) {
            while (st.count(s[right])) {
                st.erase(s[left]);
                left ++;
            }
            st.insert(s[right]);
            
            ans = max(ans, right - left + 1);
        }

        return ans;
    }
};

Python 代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        cnt = Counter() # hashmap<char, int>
        left = 0

        for right, c in enumerate(s):
            cnt[c] += 1
            
            while cnt[c] > 1:
                cnt[s[left]] -= 1
                left += 1
            
            ans = max(ans, right - left + 1)

        return ans

由于 ASCII 可见字符有 128 个，因此哈希表的大小最多为 128，或者 len(set(s))，也就是字符串 s 去重之后的长度。