题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

假设字符串中只包含从 a 到 z 的字符。

样例

输入："abcabc"

输出：3

算法

(哈希表，双指针算法) $O(n)$

用哈希表存储每个字符出现的次数，且保证区间 $[i, j]$ 内没有重复元素，每个字符只出现一次；res 记录答案

双指针扫描字符串

1. i = 0, j = 0，每次将 $s[j]$ 加入到哈希表中，$ j $ 往后移，$ i $ 不动
2. 如果 $s[j]$ 出现的次数超过 1，说明 $s[j]$ 就是重复元素，此时移动 $i$ 指针直到区间 $[i, j]$ 中没有重复元素为止
3. 计算区间长度即当前不含重复字符的字符串的长度，更新 res，res = max(res, j - i + 1)

时间复杂度

$i, j$ 最多扫描一遍字符串，所以时间复杂度为 $O(n)$

C++ 代码

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        unordered_map<int, int> count;
        int n = s.size();

        int res = 0;
        for (int i = 0, j = 0; j < n; j ++ )
        {
            if ( ++ count[s[j]] > 1)
            {
                while (count[s[i]] == 1) count[s[i]] -- , i ++ ;
                count[s[i]] -- , i ++ ;
            }
            res = max(res, j - i + 1);
        }

        return res;
    }
};