3. Longest Substring Without Repeating Characters

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

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

// int vector served as a hash table to record last occurrence index of char
int lengthOfLongestSubstring(string s) { // time: O(n); space: O(1)
    vector<int> record(128, -1); // last occurrence index
    int start = -1, res = 0;
    for (int end = 0; end < s.length(); ++end) {
        start = max(start, record[s[end]]);
        record[s[end]] = end;
        res = max(res, end - start);
    }
    return res;
}

// Sliding window
int lengthOfLongestSubstring(string s) { // time: O(n); space: O(1)
    int begin = 0, end = 0, d = 0, counter = 0;
    vector<int> record(128, 0);
    while (end < s.length()) {
        if (record[s[end++]]++ > 0) {
            counter++;
        }
        while (counter > 0) {
            if (record[s[begin++]]-- > 1) {
                counter--;
            }
        }
        d = max(d, end - begin);
    }
    return d;
}