Longest Substring Without Repeating Characters

Problem

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

A substring is a contiguous sequence of characters within a string.

Examples

Example 1:

Input: s = "zxyzxyz"

Output: 3

Example 2:

Input: s = "xxxx"

Output: 1

Constraints

• 0 <= s.length <= 1000
• s may consist of printable ASCII characters.

You should aim for a solution with O(n) time and O(m) space, where n is the length of the string and m is the number of unique characters in the string.

Solution

Move a sliding window [left, right]. Each iteration moves the window right, then move the window left to make it valid (i.e. while the window contains the new char). Once we have a valid window, insert the new character and then check for a new max length.

class Solution {
public:
    int lengthOfLongestSubstring(const std::string &s) {
        std::unordered_set<char> window_characters;
        std::size_t left = 0;
        int max_substr_len = 0;
        // Each loop will move the window right, move the left boundary up
        // until substr is valid (i.e. it doesn't contain the newly added char),
        // Then we update max size found
        for (std::size_t right = 0; right < s.size(); ++right) {
            // check if current char in window
            char c = s[right];
            while (window_characters.contains(c)) {
                window_characters.erase(s[left]);
                ++left;
            }
            // We now have a valid substr, store the new character
            window_characters.insert(c);
            max_substr_len = std::max(max_substr_len, static_cast<int>(right - left) + 1);
        }
        return max_substr_len;
    }
};