Longest Substring Without Repeating Characters

medium Strings & Sliding Window

Given a string s, find the length of the longest substring without repeating characters. A substring is a contiguous sequence of characters within the string.

Example

s = "abcabcbb"

Output: 3

The longest substring without any repeating characters is "abc", which has length 3. Other valid substrings like "bca" or "cab" also have length 3, but none longer exists without a repeated character.

Maintain a sliding window with a set of characters currently in the window. Expand the right pointer to add new characters. When you hit a duplicate, shrink the window from the left by removing characters until the duplicate is gone. The longest valid window seen during this process is your answer.

Why this works

A sliding window lets you efficiently explore all substrings without repeating characters. Expand the right side to grow the window; when a duplicate appears, shrink from the left until it is gone. The set tracks what is currently in the window, giving O(1) duplicate checks.

Step by step

Expand the window — move the right pointer forward, adding each character to the set.
Handle duplicates — if the new character is already in the set, remove characters from the left until it is not.
Track the best — after each expansion, compare the current window size to the max seen so far.

Time: O(n) Space: O(min(n, 26))

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> charSet = new HashSet<>();
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            while (charSet.contains(s.charAt(right))) {  // shrink window until no duplicates
                charSet.remove(s.charAt(left));
                left++;
            }
            charSet.add(s.charAt(right));  // expand window with new character
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> charSet;
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.size(); right++) {
            while (charSet.count(s[right])) {  // shrink window until no duplicates
                charSet.erase(s[left]);
                left++;
            }
            charSet.insert(s[right]);  // expand window with new character
            maxLen = max(maxLen, right - left + 1);
        }
        return maxLen;
    }
};

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:       # shrink window until no duplicates
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])            # expand window with new character
        max_len = max(max_len, right - left + 1)
    return max_len