Longest Substring Without Repeating Characters

+10

You get a string s. Find the longest substring, a run of characters that sit next to each other, in which no character appears twice, and return its length.

Uppercase and lowercase letters count as different characters, so a and A are not a repeat.

Function

lengthOfLongestSubstring(s: string) → integer

sstring: the string to search
Returnsinteger: the length of the longest substring with no repeated character

Constraints

1 ≤ s.length ≤ 5 × 10⁴
s holds only English letters (lowercase and uppercase) and digits.
Uppercase and lowercase letters are different characters.

Examples

Input: s = "coddycode"
Output: 5
Explanation: ycode holds five different characters. Adding the d before it gives dycode, with d twice, and no other run of five or more avoids a repeat.

Input: s = "racecar"
Output: 4
Explanation: Both race and ecar have four different letters. Every run of five letters contains the same letter twice.

Input: s = "a1b2a3b"
Output: 5
Explanation: Digits count as characters too, so 1b2a3 has five different ones. Both runs of six hold a second a or a second b.

Follow-up

What would you change if s could hold any Unicode character instead of letters and digits?

Solution

Keep a window: two edges around a run with no repeated character. The right edge reads each character once and the left edge only moves forward, so one pass finds, for every end, the longest run without repeats that ends there.

Check every substring

Correct, but does not finish on the largest tests

Intuition

Try every start and end, and test each substring by adding its characters to a set until one is already there. Every candidate gets tested, so the longest valid one cannot be missed.

There are about n²/2 substrings, 1.25 × 10^9 for n = 5 × 10^4, and a test can read up to n characters: O(n³). Here a test stops after at most 63 characters, since the string holds only 62 different ones, but that still leaves over a billion tests.

Algorithm

Set best to 0.
For every start index, loop over every end index from the start to the end of the string.
Add the substring's characters to an empty set one by one, and stop at the first one already in the set.
If no character repeated and the substring beats best, store its length.
Return best.

def lengthOfLongestSubstring(s):
    def has_no_repeat(start, end):
        seen = set()
        for k in range(start, end + 1):
            if s[k] in seen:
                return False
            seen.add(s[k])
        return True

    best = 0
    n = len(s)
    for start in range(n):
        for end in range(start, n):
            if has_no_repeat(start, end):
                best = max(best, end - start + 1)
    return best

Sliding window with a set

Intuition

If abc has no repeat, testing abcd needs one question: is d among a, b and c? A set of the window's characters answers it at once.

Move right one step at a time. If the new character is in the set, remove characters from the left until its earlier copy is gone, then add it and measure. You drop characters only when you must, so for each right the window is the longest run without repeats ending there, and the best substring ends somewhere. Each character enters the set once and leaves at most once: O(n).

Algorithm

Start with an empty set, left = 0 and best = 0.
Move right over every index.
While s[right] is in the set, remove s[left] and move left one step forward.
Add s[right] to the set.
If right - left + 1 beats best, store it.
Return best.

def lengthOfLongestSubstring(s):
    in_window = set()  # the characters between left and right
    left = 0
    best = 0
    for right in range(len(s)):
        # Shrink from the left until s[right] is no longer inside.
        while s[right] in in_window:
            in_window.remove(s[left])
            left += 1
        in_window.add(s[right])
        best = max(best, right - left + 1)
    return best

Sliding window that jumps to the last-seen index

Intuition

You already know where left must land: one past the earlier copy of the new character. Store each character's last index, in a map or an array with one slot per character code, and left jumps there in one step.

Jump only when that index is at or after left. An older copy is already outside the window, and jumping to it would move left backward. The window at every step is the one the set version builds, and each character now costs one lookup, one comparison and one write.

Algorithm

Create an empty map from character to last index, and set left = 0 and best = 0.
Move right over every index, reading the character ch there.
If ch was last seen at or after left, set left to that index plus one.
Record right as the last index of ch.
If right - left + 1 beats best, store it.
Return best.

def lengthOfLongestSubstring(s):
    last_seen = {}
    start = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = i
        if i - start + 1 > best:
            best = i - start + 1
    return best

Pitfalls and edge cases

Moving left backward. In abba, the earlier a at index 0 is already outside the window when you reach the last a. Jumping to index 1 brings the second b back and gives 3 instead of 2.
Counting the window as right - left. Both ends are inside it, so add one.
Lowercasing the string first. a and A are different characters here, so aA has length 2.
Measuring only when a repeat appears. A string with no repeat, like z, never triggers it, and the answer comes out as 0.

Frequently asked questions3

What is the time complexity of Longest Substring Without Repeating Characters?

The sliding window runs in O(n) time, where n is the length of the string: the right edge reads each character once and the left edge only moves forward. Extra space is O(k), where k is the number of different characters the string can hold, 62 here.

Should you use a hash map or an array for the last indices?

Both give O(n) time. With a small fixed set of characters, as here, an array indexed by character code avoids hashing and is faster.

What is the difference between a substring and a subsequence?

A substring is a block of characters that sit next to each other, like ode in coddycode. A subsequence may skip characters, like cdy. This problem asks for a substring, which is why a window with two edges works.

def lengthOfLongestSubstring(s):
    # Write code here

Test #1

Test #2

Test #3

Argument

s = "coddycode"

Expected Output

Longest Substring Without Repeating Characters

Function

Constraints

Examples

Hints

Solution

Check every substring

Sliding window with a set

Sliding window that jumps to the last-seen index

Pitfalls and edge cases

Frequently asked questions3

Similar problems