~/leetcode $ 3. Longest-Substring-Without-Repeating-Characters

We want to find the longest substring without repeating characters (where substrings are contiguous characters in the string). Because it is contiguous, it lends itself well to a sliding window approach.

So if we let our current window be the current longest substring without repeating characters, we know how to extend and shrink our window. We keep extending our window to the right until we come across a character that is already in the current window. Then, when we do, we can shrink our window (from the left) until the character in conflict is no longer in the window. We can keep doing this until the end of the list, updating the longest substring without repeating characters that we have seen.

If we instantiate left and right pointers to denote the start and end of the window, we increment the right pointer to expand the list and increment the left pointer to shrink the list. The length of the window is right - left and we can keep track of the current elements in the window by using a hashset (so that insert, remove and lookup are all O(1)).

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int longest = 0;
        int l = 0;
        int r = 0;
        unordered_set<char> seen {};

        while (r < s.size()) {
            while (seen.contains(s[r])) {
                seen.erase(s[l]);
                ++l;
            }
            seen.insert(s[r]);
            ++r;
            longest = max(longest, r - l);
        }

        return longest;
    }
}

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: 5m 58s