Longest Substring Without Repeating Characters

Problem Description

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, not a subsequence.

Examples

Constraints

• 0 ≤ s.length ≤ 5 * 10⁴
• s consists of English letters, digits, symbols, and spaces.

The Window Shrinks When You See the Same Character Twice

The brute force picks every possible starting index and scans right until it hits a duplicate. That’s O(n²) because you restart from scratch each time. The question is: when you hit a duplicate at index j, do you really need to restart from i + 1? No. You only need to move the left boundary forward past the previous occurrence of that character.

That’s the sliding window insight: maintain a window [left, right] that always contains only unique characters. When right encounters a character that’s already inside the window, don’t restart, just advance left to one position past where that character last appeared. The window never contracts more than it needs to.

Solution 1: Brute Force

Check every possible starting index and scan right, tracking characters with a set. Reset the set each time you move to a new start.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = i; j < s.length(); j++) {
                if (seen.contains(s.charAt(j))) break;
                seen.add(s.charAt(j));
                result = Math.max(result, j - i + 1);
            }
        }
        return result;
    }
}

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = 0
        for i in range(len(s)):
            seen = set()
            for j in range(i, len(s)):
                if s[j] in seen:
                    break
                seen.add(s[j])
                result = max(result, j - i + 1)
        return result

#include <string>
#include <unordered_set>

class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        int result = 0;
        for (int i = 0; i < s.size(); i++) {
            std::unordered_set<char> seen;
            for (int j = i; j < s.size(); j++) {
                if (seen.count(s[j])) break;
                seen.insert(s[j]);
                result = std::max(result, j - i + 1);
            }
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n²). Two nested loops over the string.
• Space Complexity: O(min(n, m)). The set holds at most the size of the character set m or the string length n.

Where it breaks: On a 50,000-character string with all unique characters, this is 1.25 billion operations. Not acceptable.

Solution 2: Sliding Window with Hash Map

Store each character’s most recent index in a hash map. When right encounters a character that’s already in the map, jump left to map[char] + 1. This skips right past the duplicate without re-scanning.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int left = 0, result = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
                // jump left past the previous occurrence, not just one step
                left = lastSeen.get(c) + 1;
            }
            lastSeen.put(c, right);
            result = Math.max(result, right - left + 1);
        }
        return result;
    }
}

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}
        left = 0
        result = 0

        for right, c in enumerate(s):
            if c in last_seen and last_seen[c] >= left:
                # jump left past the previous occurrence, not just one step
                left = last_seen[c] + 1
            last_seen[c] = right
            result = max(result, right - left + 1)

        return result

#include <string>
#include <unordered_map>

class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        std::unordered_map<char, int> lastSeen;
        int left = 0, result = 0;

        for (int right = 0; right < s.size(); right++) {
            char c = s[right];
            if (lastSeen.count(c) && lastSeen[c] >= left) {
                // jump left past the previous occurrence, not just one step
                left = lastSeen[c] + 1;
            }
            lastSeen[c] = right;
            result = std::max(result, right - left + 1);
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Each character is visited at most twice: once by right, possibly once when left jumps.
• Space Complexity: O(min(n, m)). The map holds at most as many entries as characters in the input (bounded by character set size).

Where it breaks: the lastSeen.get(c) >= left check is easy to forget. Without it, left can jump backward if the same character appeared before the current window started, shrinking the window incorrectly.

Why Not Use a Simple Set Instead of a Map?

A set works, but requires you to manually shrink the window by removing characters one at a time from the left (O(n) total shrink operations) rather than jumping directly. The logic is more code for the same complexity. The map version is faster to write and less error-prone in an interview.

Common Mistakes

• Forgetting the >= left bound check. If a character appeared before the current window, its stale map entry would incorrectly move left backward. Always guard against this.
• Confusing substring with subsequence. The problem asks for a contiguous substring. “pwke” from “pwwkew” doesn’t count because “w” at index 2 is skipped.
• Off-by-one on window size. The window length is right - left + 1, not right - left. Missing the +1 means you undercount by one on every window.

Frequently Asked Questions

Does this work for Unicode strings, not just ASCII? Yes. The hash map handles any character type. If the input is restricted to ASCII (128 chars) or lowercase letters (26 chars), you can swap the map for a fixed-size array for a small constant speedup.

What if the string is empty? The loop never executes and result stays 0, which is correct. No special casing needed.

How is this different from the minimum window substring problem? Minimum Window Substring requires all characters of a target to be present in the window. This problem just requires all characters in the window to be unique. Same sliding window mechanics, different validity condition.

← All Problems