题目描述

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

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

样例

输入："abcabc"

输出：3

算法

(双指针)

1. i和j分别为双指针，i为终点，j为起点。每当有重复元素出现，起点j往前走一步，对应的字符要删去。
2. 注意：判断的时候是while(s[i] > 1)而不是while(s[j] > 1)，因为i是遍历到新字符的那个指针。

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        // vector<int> arr;
        unordered_map<char, int> arr;
        int res = 0;
        for(int i = 0, j = 0; i < s.size(); i ++)
        {
            arr[s[i]] ++;
            while(j < s.size() && arr[s[i]] > 1)
            {
                arr[s[j]] --;
                j ++;
            }
            res = max(res, i - j + 1);
        }
        return res;
    }
};