Longest Substring Without Repeating…

Approach Summary

Use a sliding window with a hash set. Expand right; when a duplicate is found, shrink from the left until the window is valid again.

Full Solution & Approach

The brute force checks every substring and tests uniqueness with a set — O(n³) or O(n²) depending on implementation. The sliding window version notices that as the window expands to the right, the left boundary only ever moves right, never back. Maintain two pointers, left and right, over the string and use a set to store the characters currently inside the window. Expand right and add s[right]. If s[right] is already in the set, the window is invalid: shrink from the left by removing s[left] and advancing left until the duplicate is gone. After each step the window is a valid substring with all-unique characters, so record max(right - left + 1). Every character is added once and removed at most once, so the two-pointer scan is linear. The key insight: because any valid window ending at right is superseded once right advances, we never need to revisit a left position.

Each character enters the window once (right advances) and leaves at most once (left advances), so the total work is bounded by 2n — O(n). The set stores at most the distinct characters in the current window; with a bounded alphabet this is O(min(n, alphabet)) ≈ O(1) in practice.

Solution Code

Solution

def length_of_longest_substring(s: str) -> int:
    seen = set()
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)
    return best

function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

public int lengthOfLongestSubstring(String s) {
    Set<Character> seen = new HashSet<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        while (seen.contains(s.charAt(right))) {
            seen.remove(s.charAt(left));
            left++;
        }
        seen.add(s.charAt(right));
        best = Math.max(best, right - left + 1);
    }
    return best;
}

int lengthOfLongestSubstring(const string& s) {
    unordered_set<char> seen;
    int left = 0, best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        while (seen.count(s[right])) {
            seen.erase(s[left]);
            left++;
        }
        seen.insert(s[right]);
        best = max(best, right - left + 1);
    }
    return best;
}

Edge Cases to Watch

Empty string — return 0
All identical characters like "aaaa" — the window never grows past length 1
Single character — return 1
Unicode characters — the set keys on any character, so it still works

How to Recognize This Pattern

Asks for longest substring
Unique character constraint

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(min(n, alphabet))

Longest Substring Without Repeating Characters