Skip to main content
DSA patterns

Longest Substring Without Repeating Characters

mediumSliding window Must-doAmazonMetaGoogle

Problem statement

You're given a string s. Find the length of the longest stretch of consecutive characters in s where no character repeats.

Think of s as a stream of log tokens or request IDs read one character at a time — you want to know the longest run you can read before you'd see the same token twice, which is a useful check when validating that a window of recent activity has no repeats (like catching a client hammering the same endpoint back-to-back).

Examples

Example 1

Input: s = "abcabcbb"

Output: 3

Explanation: The longest stretch with no repeated character is "abc", which has length 3. "bca" and "cab" are equally valid answers, since the question only asks for the length.

Example 2

Input: s = "pwwkew"

Output: 3

Explanation: The longest stretch with no repeat is "wke", length 3. Note that "pwke" is *not* valid — its characters aren't consecutive in s, so it's a subsequence, not a substring.

Hints

Hint 1: Checking every possible substring for repeated characters works, but building and checking each one takes its own pass, which adds up fast.

Approach

Optimal: Sliding window with last-seen index

Intuition

The better approach still wastes work: after finding a repeat, it throws away everything it learned about the window and restarts from scratch at the next starting position. But you already know exactly where the repeat came from — so instead of restarting, just jump the window's left edge to just past the previous occurrence of the repeated character, and keep going. A hash map that remembers the last position each character was seen at makes that jump an O(1) lookup, which is what removes the wasted re-scanning.

Steps

  1. Keep a hash map last_index (character → its most recent index), a left pointer starting at 0, and a running best.
  2. For each position right in the string, with character ch = s[right]:
    • If ch was seen before and that earlier occurrence is still inside the current window (its index is >= left), move left to just past it.
    • Record ch's current position in last_index.
    • Update best if the current window's length (right - left + 1) is larger.
  3. Return best.

Dry run

s = "pwwkew"

right ch last_index[ch] before left before action left after window length best
0 p — 0 new char 0 1 1
1 w — 0 new char 0 2 2
2 w 1 0 repeat in window → left = 2 2 1 2
3 k — 2 new char 2 2 2
4 e — 2 new char 2 3 3
5 w 2 2 repeat (index 2) not ≥ left (2)? it is ≥ 2 → left = 3 3 3 3

The best window length found, 3, matches the example ("wke").

Edge cases: an empty string never enters the loop, so best stays 0; the check last_index[ch] >= left (not just "have we seen ch before") is what correctly ignores a character's old occurrence once it has already fallen outside the current window.

Complexity

Time O(n) - each character is visited by the right edge of the window exactly once, and the left edge only ever moves forward

Space O(min(n, m)) - a hash map holds at most one entry per distinct character seen, where `m` is the size of the character set.

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


if __name__ == "__main__":
    print(Solution().lengthOfLongestSubstring("abcabcbb"))  # 3
    print(Solution().lengthOfLongestSubstring("bbbbb"))  # 1
    print(Solution().lengthOfLongestSubstring("pwwkew"))  # 3
RecapThe whole problem in a few lines, for the night before
  • Spot it: "longest run of a string/array with no repeated element" — a sliding window over a sequence
  • Idea: expand the window's right edge; when a repeat is found, jump the left edge to just past that character's last seen index using a hash map
  • Cost: O(n) time, O(min(n, m)) space for the character-set size m
  • Trap: jumping left on *any* previous sighting of a character, not just one still inside the window, can move left backward and break the window — always check the stored index is >= left first

Interview follow-ups

  • What if you needed to return the actual longest substring, not just its length?

    Track the left and right values at the moment best is updated (or just re-slice s[left:right+1] once the loop finishes, using the saved indices), instead of only comparing lengths. Still O(n) time and O(min(n, m)) space — one more pair of saved indices doesn't change the complexity.

  • What if the string is streamed character by character and you need the current longest run at any moment, without storing the whole string?

    The same sliding-window state — last_index, left, and best — can be updated incrementally as each character arrives, in O(1) time per character, without ever needing to look back at earlier characters directly. The map does need to be trimmed occasionally in a truly unbounded stream (dropping entries whose index has fallen behind left) to keep memory bounded by the current window size rather than the whole stream's history.

Frequently asked questions

A character can appear earlier in the string but outside the current window — for example in "abba", when the second a is reached, left has already moved past the first a. If you jumped left every time a character was ever seen before, left could move backward, which would corrupt the window. Checking that the earlier occurrence is still >= left guarantees the jump only ever moves left forward.

Scanning a stream of tokens (log lines, request IDs, client connections) for the longest run without a repeat is a real check for anomaly detection — for example, confirming a session doesn't replay the same request ID twice within a window, or measuring how long a sequence of unique client IPs runs before one repeats. It's also a standard test of whether a candidate can recognize that a two-pointer window with a "jump" can replace an O(n²) restart-from-scratch scan.

A set can only answer "have I seen this character in the current window?" — it can't tell you where. To jump left directly to just past the repeat (instead of removing characters one at a time until the duplicate is gone), you need to know the repeated character's exact previous index, which only a map (character → last index) can give you in O(1).

Yes — with a single repeated character (example 2, "bbbbb"), every new occurrence immediately triggers a jump of left to right after the previous one, keeping the window length at exactly 1 throughout, which is correct since no window of size 2 or more can avoid repeating that one character.