Longest Substring Without Repeating Characters

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

分析

维护一个滑动窗口：
- 滑动窗口用两个指针表示，j 为窗口左端，i 为窗口右端
- 窗口内的子串为 [j, i]，保证该窗口内没有重复字符
使用哈希表记录字符出现的次数：
- 哈希表 hash 的 key 为字符，value 为该字符在窗口中的出现次数
移动窗口右端：
- 遍历字符串，右端指针 i 每次右移一格，将字符加入窗口并更新哈希表
处理重复字符：
- 如果窗口中出现重复字符（即当前字符的出现次数大于 1），移动左端指针 j，并在哈希表中移除字符，直到窗口内没有重复字符。
更新结果：
- 每次移动窗口时，计算当前窗口的长度 (i - j + 1)，并更新结果 res

时间复杂度

每个字符至多被访问两次（右指针扩展时访问一次，左指针收缩时访问一次），时间复杂度为 O(n)

空间复杂度

使用哈希表存储字符出现次数，空间复杂度为 O(k)，其中 k 为字符集大小

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        std::unordered_map<char, int> hash; // 记录字符出现次数
        int res = 0; // 最长子串长度

        for (int i = 0, j = 0; i < s.size(); ++ i)
        {
            ++hash[s[i]]; // 将字符加入窗口

            // 如果出现重复字符，移动左指针 j
            while (hash[s[i]] > 1)
            {
                -- hash[s[j]];
                ++ j;
            }

            // 更新最长子串长度
            res = std::max(res, i - j + 1);
        }

        return res;
    }
};