Longest Substring Without Repeating Characters

Sliding Window Medium

Python Java C++

def lengthOfLongestSubstring(s: str) -> int:
    # Map to store last position of each character
    charMap = {}
    start = 0   # Window start position
    maxLen = 0  # Track maximum length found
    
    # Iterate through string using end pointer
    for end in range(len(s)):
        char = s[end]
        # If char seen and after start, update start
        if char in charMap and charMap[char] >= start:
            start = charMap[char] + 1
            
        # Update maximum length with current window
        maxLen = max(maxLen, end - start + 1)
        # Store current char position
        charMap[char] = end
        
    return maxLen

// This is best solution from discussion section.
class Solution {
public int lengthOfLongestSubstring(String s) {
        // Map to store last position of each character
        Map map= new HashMap<>();
        // Track window start and maximum length
        int start=0, len=0;
        
        for(int i=0; i < s.length(); i++) {
            char c = s.charAt(i);
            // If char already seen and after window start
            if (map.containsKey(c)) {
                if (map.get(c) >= start) 
                    start = map.get(c) + 1;
            }
            // Update maximum length with current window
            len = Math.max(len, i-start+1);
            // Store current char position
            map.put(c, i);
        }
        
        return len;
    }
}

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // Map to store last position of each character
        unordered_map charMap;
        int start = 0;   // Window start position
        int maxLen = 0;  // Track maximum length found
        
        // Iterate through string using end pointer
        for (int end = 0; end < s.length(); end++) {
            char c = s[end];
            // If char seen and after start, update start
            if (charMap.count(c) && charMap[c] >= start)
                start = charMap[c] + 1;
            
            // Update maximum length with current window
            maxLen = max(maxLen, end - start + 1);
            // Store current char position
            charMap[c] = end;
        }
        
        return maxLen;
    }
};

Previous Step Next Step Reset

Window Start

0

Current Length

0

Max Length

0

Character Position Map

Click "Next Step" to begin the visualization

Problem Statement

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

Detailed Explanation

Approach

This solution uses a sliding window approach with a hash map to track character positions. Instead of explicitly checking for duplicates, we use character positions to efficiently update the window start position when duplicates are found.

Key Concepts

1. Character Position Map: Store most recent position of each character
2. Smart Window Start: Jump start pointer directly to after duplicate
3. Length Tracking: Update maximum length after each window change
4. Position Comparison: Only update start if duplicate is within current window

Algorithm Steps

1. Initialize tracking variables:
   • Map for character positions
   • start: window start position
   • maxLen: maximum length found
2. For each character position (i):
   • If character seen before and after start:
     • Move start to after previous occurrence
   • Update maximum length
   • Store current character position

Time and Space Complexity

• Time Complexity: O(n) - Single pass through string
• Space Complexity: O(min(m,n))
  • n is string length
  • m is character set size
  • Map stores at most min(m,n) characters

Why This Works

The solution is optimal because:

• Direct Jump:
  • No need to check each character in window
  • Jump directly to valid start position
  • Avoids unnecessary sliding
• Position Tracking:
  • Map gives O(1) access to last position
  • Comparison with start ensures window validity
  • No need for set to track current window

Edge Cases

• Empty string: Return 0
• Single character: Return 1
• All same characters: Return 1
• No repeating characters: Return string length
• Repeats outside window: Keep current window

Common Mistakes

• Not checking if duplicate is within current window
• Incorrect window length calculation
• Not updating map with latest position
• Using set instead of map (less efficient)
• Unnecessary window shrinking