Blog

Longest Substring Without Repeating Characters

Candidates have reported being asked to find the longest substring without repeating characters at eBay, Microsoft, and Rakuten. A substring is a consecutive part of a string; we need the length of the longest one with no repeated characters.

abba2

Check substrings incrementally

If we try every pair of endpoints and recheck each substring from scratch with a fresh set, we can take O(n³) expected time on an all-distinct input and use O(n) extra space. Here, n is the string length.

We can avoid rescanning each substring. For each starting position, create an empty set, extend to the right one character at a time, and stop at the first repeat. Add each new character to that same set as we extend. With expected constant-time set operations, we take O(n²) expected time in the worst case and use O(n) extra space.

Keep a sliding window

We can also avoid starting over at each position. Scan once and store each character's most recent index in a map. When we see a character again, move the left boundary past its earlier occurrence if that occurrence is inside the window. Otherwise, keep the current boundary.

abbaabbaabba

In abba, we first extend through ab. When we read the second b, move the left boundary past the earlier b to index 2. At the final a, its earlier occurrence at index 0 is already outside the window, so keep the window ba.

Use max(left, last_seen[char] + 1) to keep the left boundary from moving backward, and record the greatest valid window length as we go.

Python
def longest_unique_substring(text):
    last_seen = {}
    left = 0
    best = 0
    for right, char in enumerate(text):
        if char in last_seen:
            left = max(left, last_seen[char] + 1)
        last_seen[char] = right
        best = max(best, right - left + 1)
    return best

We take O(n) expected time and use O(min(n, k)) extra space, where k is the number of possible character values. In Python, we process Unicode code points.

For CodeCrack's Variety Span, use integer genre IDs rather than characters. In the full walkthrough, we use a set-based sliding window.