Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without 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 a substring, "pwke" is a subsequence and not a substring.

Solution: Sliding Window

We can slide the left side of the window to the right when we found a duplicate character. The worst case of this solution requires O(2*N)

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> m;
    int left=0, maxLength=0;

    for (int i=0; i<s.length(); i++) {
        m[s[i]] += 1;

        // Shrink window while we found duplicate characters
        while (m[s[i]] > 1 && left < i) {
            m[s[left]] -= 1;
            left += 1;
        }

        maxLength = max(maxLength, i-left+1);            
    }

    return maxLength;
}

Solution: Sliding Window Optimized

In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.

Note: We don't have to remove anything while we update our left pointer.

Time Complexity: O(N)

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> m;
    int left = 0, ans = 0;

    for (int i=0; i<s.length(); i++) {
        if (m.find(s[i]) != m.end()) {
            left = max(m[s[i]]+1, left);
        }             
        ans = max(ans, i-left+1);
        m[s[i]] = i+1;
    }

    return ans;
}