leetcode/3_gp.cpp at dev · xcheng85/leetcode · GitHub

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
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int result = 0;

        unordered_map<char, int> myCache;
        int currentLength = 0;
        int minValidIndex = 0;  // key issue
        for(int i = 0; i < s.size(); i++){
            if(myCache.find(s[i]) == myCache.end() || myCache[s[i]] < minValidIndex){
                myCache[s[i]] = i;
                currentLength++;
            }else{
                int prevPos = myCache[s[i]];
                minValidIndex = prevPos + 1;

                myCache[s[i]] = i;

                result = max(result, currentLength);
                currentLength = i - prevPos;
            }
        }
        return max(result, currentLength);
    }
};