3. Longest Substring Without Repeating Characters

Given a string, find the length of thelongest substringwithout repeating characters.

Examples:

Given"abcabcbb", the answer is"abc", which the length is 3.

Given"bbbbb", the answer is"b", with the length of 1.

Given"pwwkew", the answer is"wke", with the length of 3. Note that the answer must be asubstring,"pwke"is asubsequenceand not a substring.

Thoughts:

count: count word repeating trigger

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0, right = 0, count = 0, len = 0;
        unordered_map <char, int> map;
        while(right< s.length()){
            if(++map[s[right]] == 2) count++; // can also be ++map[s[right]] > 1
            right++;

            while(count == 1){    // can also be count > 0
                if(--map[s[left]] == 1) count --; // can also be --map[s[left]] > 0
                left++;
            }

            len = max(len, right - left);
        }

        return len;
    }
};

Code: C++ Template

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> map(128,0);
        int counter=0, begin=0, end=0, d=0; 
        while(end<s.size()){
            if(map[s[end++]]++ >0) counter++; 
            while(counter > 0) if(map[s[begin++]]-->1) counter--; // or counter == 1
            d = max(d, end-begin); //while valid, update d
        }
        return d;
    }
};