MediumHash TableStringSliding Window

Longest Substring Without Repeating Characters

1 approach, code in every language

Given a string s, measure the longest stretch of consecutive characters in which every character is unique. Return that length as an integer.

The characters must be adjacent in the original string; picking scattered characters is not allowed.

Example 1

Input: s = "abcabcbb"

Output: 3

The block "abc" has no repeats and is as long as any repeat-free stretch here.

Example 2

Input: s = "bbbbb"

Output: 1

Every character is the same, so the longest unique stretch is a single b.

Constraints

0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols, and spaces.

Sliding window with last-seen index

Slide a window across s and jump the left edge forward whenever a repeat appears, using a table that stores the most recent index of each character.

Loading animation…

Intuition

A repeat-free window is defined entirely by its left boundary: as soon as the incoming character was seen inside the current window, the boundary must move just past that earlier occurrence. Storing each character's latest position lets the left edge leap directly to the right spot instead of stepping one by one, so the whole string is scanned once while the window length is tracked at every step.

Algorithm walkthrough

1Keep a map from character to the last index where it appeared, and a left pointer marking the window start.
2Walk the right pointer across the string one character at a time.
3If the current character was seen at or after the left pointer, move left to one past that stored index.
4Record the current index for the character and update the best length with the current window size.
5After the scan finishes, the best length is the answer.

Implementation

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

Time

O(n)

Space

O(min(n, a))

a is the size of the character set; each index is visited once by each pointer.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

After the pattern

Now solve one you haven't seen.

Largest Clean Tap Block is our own problem on the technique behind Longest Substring Without Repeating Characters: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free