Longest Substring Without Repeating Characters

Medium Problem 22 of 151 Java and Python

Problem

Given a string s, return the length of the longest substring (a contiguous run of characters) that contains no repeated characters.

Example 1

Input: s = "abcabcbb"
Output: 3
Why: "abc" is the longest such substring.

Example 2

Input: s = "bbbbb"
Output: 1
Why: "b".

Example 3

Input: s = "pwwkew"
Output: 3
Why: "wke". Note that "pwke" is a subsequence, not a substring.

Constraints

0 ≤ s.length ≤ 5 × 10⁴
s contains English letters, digits, symbols and spaces.

Explanation

Keep a window [left, right] with no repeats. Extend it to the right one character at a time. When the new character already appears inside the window, the window must start just after that earlier copy.

Remembering the last index of every character lets the left edge jump straight there instead of shrinking one step at a time.

Approach 1 · Naive

Grow from every start

Time O(n · m), m = alphabet size (O(n²) in general)
Space O(m)

From each starting index, extend to the right with a set of seen characters until a repeat appears.

For each i, start an empty set.
For j from i: stop if s[j] is in the set, otherwise add it and update the best length j - i + 1.

Java

import java.util.*;

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

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        best = 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])
                best = max(best, j - i + 1)
        return best

Approach 2 · Optimal

Sliding window with last positions

Time O(n)
Space O(m)

Walk right through the string. If s[right] was last seen at or after left, move left to one past that position. The window is then repeat-free.

Keep a map last from character to its most recent index, and left = 0.
For each right: if last[c] >= left, set left = last[c] + 1.
Store last[c] = right and update the best with right - left + 1.

Java

import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int left = 0;
        int best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (last.containsKey(c) && last.get(c) >= left) {
                left = last.get(c) + 1;
            }
            last.put(c, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}
        left = best = 0
        for right, c in enumerate(s):
            if last.get(c, -1) >= left:
                left = last[c] + 1
            last[c] = right
            best = max(best, right - left + 1)
        return best

Complexity compared

Approach	Time	Space
Naive Grow from every start	O(n · m), m = alphabet size (O(n²) in general)	O(m)
Optimal Sliding window with last positions	O(n)	O(m)

Key takeaways

The check last[c] >= left matters: an old copy outside the window must not pull left backwards.
Sliding window template: expand right every step, shrink left only when the window breaks the rule.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem