Domain 2MediumCORE

Longest Substring Without Repeating Characters

We need to find the maximum length of a contiguous substring where every character is unique (no duplicates allowed within that specific window). - Input: A string s containing letters, digits, symbols. Length up to 50k. - Output: An integer representing the max length found. - Edge Cases: Empty string ('') should return 0. Strings with all identical characters (e.g., 'bbbbb') should return 1. Subsequences are not allowed; order and contiguity matter.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#Two Pointers#String#Sliding Window

3. Longest Substring Without Repeating Characters

Model: qwen3.5:9b
Topics: Hash Table,Two Pointers,String,Sliding Window
FAANG asked: 1
Acceptance rate: 31.5%


Problem Breakdown

We need to find the maximum length of a contiguous substring where every character is unique (no duplicates allowed within that specific window).

  • Input: A string s containing letters, digits, symbols. Length up to 50k.
  • Output: An integer representing the max length found.
  • Edge Cases: Empty string ("") should return 0. Strings with all identical characters (e.g., “bbbbb”) should return 1. Subsequences are not allowed; order and contiguity matter.

Intuition

A naive brute-force approach would iterate through every possible substring, check for duplicates in each one using a set or sorting, and track the max length. This results in O(N^3) time complexity because there are N*(N+1)/2 substrings, and checking uniqueness takes linear time relative to window size.

We can optimize this by observing that as we expand our right pointer (right), if we encounter a character already present in our current valid window, the new substring cannot start before or at the previous occurrence of that duplicate character. Instead of resetting left all the way back to 0 every time, we only need to move left past the last seen index of the repeating character. This suggests an O(N) solution using a Sliding Window pattern combined with a Hash Map (dictionary in Python) to store the most recent index of each character encountered so far.

Approach

  1. Initialize two pointers: left = 0, and track max_len.
  2. Use a dictionary (char_map) to store the last seen index for every unique character.
  3. Iterate with right from 0 to length-1:
    • Check if current char s[right] is in our map AND its stored index is >= left. This means it’s inside our current window (a duplicate).
    • If a valid duplicate exists, move left to char_map[s[right]] + 1. We discard the substring up to and including that previous occurrence.
    • Update max_len = max(max_len, right - left + 1).
    • Always update the map with the current index of s[right], even if it was a duplicate (to track its new position).

Complexity Analysis

  • Time: O(N), where N is length of string. We traverse the string once; dictionary operations are amortized O(1). The left pointer moves forward at most as many times as the right pointer, so total movements for both pointers combined is 2N.
  • Space: O(min(M, K)), where M is alphabet size (ASCII/Unicode) and K is number of unique characters in s. In practice bounded by constant space if charset is fixed, or proportional to string length otherwise.

Solution

def lengthOfLongestSubstring(s: str) -> int:
    char_map = {}  # Stores last index of each character
    left = 0       # Left pointer for sliding window
    
    max_len = 0
    
    for right, char in enumerate(s):
        if char in char_map and char_map[char] >= left:
            # Duplicate found within current window. 
            # Move left past the previous occurrence of this character.
            left = char_map[char] + 1
        
        # Update last seen index to current position for future checks
        char_map[char] = right
        
        # Calculate current valid substring length and update max_len
        max_len = max(max_len, right - left + 1)
        
    return max_len

Edge Cases Handled

  • Empty String: Loop does not execute; max_len remains initialized to 0. Correctly returns 0.
  • All Duplicates (e.g., “bbbbb”): On second ‘b’, left jumps past the first index, window size becomes 1 repeatedly. Returns 1.
  • No Duplicates: char_map check fails every time; max_len grows to full string length N.
  • Duplicate at End of String: Logic correctly updates map and calculates final valid substring ending before or including current char depending on previous duplicates.