Given a string s, find the length of the longest substring without repeating characters.

---

Solution 1

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> dict;
        int ans=0,i=0,j=0;
        for(;i<s.size();i++){
            if(dict.count(s[i]) && dict[s[i]]>j){
                ans=max(i-j,ans);
                j=dict[s[i]];
            }
            dict[s[i]]=i+1;
        }
        ans=max(ans,i-j);
        return ans;
    }
};

通过哈希表存储字符值对应的下一个索引位置，i-j维持着不重复字符序列的左右两边。一旦右索引检测到哈希表中存在某值的下一个索引且这个索引位置大于序列左边的索引，则将左边向右移到哈希表存储的值的位置，变窄。