DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Longest Substring Without Repeating Characters

mediumSliding window Must-do

Problem statement

Given a string s, find the longest contiguous run of characters in which no character appears twice, and return its length. The string can contain letters, digits, spaces and symbols, and it can be empty.

Examples

Example 1

Input: s = "deploydev"

Output: 7

Explanation: "ploydev" has seven different characters. Any longer stretch repeats a "d" or an "e".

Example 2

Input: s = "aaaa"

Output: 1

Explanation: Every stretch longer than one character repeats "a".

Hints

Approach

Use a variable-size sliding window [left, right] that always holds distinct characters, plus a map from each character to the last index where it appeared.

  1. Set left = 0 and an empty map last.
  2. For each right, let ch = s[right]. If ch was seen at an index >= left, it is inside the window, so move left to last[ch] + 1.
  3. Record last[ch] = right and update the best length right - left + 1.
  4. Return the best length.

The check last[ch] >= left matters: a character seen before the window started is not a duplicate. In "abba", when the final a arrives the window is "b" (starting at index 2), and the old a at index 0 must not pull left backwards.

A simpler variant keeps a set and moves left one step at a time while removing characters. It is also O(n), but does up to two passes over the string.

ComplexityTime O(n)Space O(min(n, a))
Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
last = {} # character -> last index seen
left = 0
best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1 # jump past the earlier copy
last[ch] = right
best = max(best, right - left + 1)
return best

Follow-up questions

  • Return the substring itself, not just its length.
  • Allow each character to appear at most twice in the window.

Frequently asked questions

It is the size of the character set. The map never holds more distinct characters than exist, so space is bounded by both the string length and the alphabet size.

Restarting from the repeated character's position throws away valid work and can miss answers. Moving left to just past the earlier copy keeps everything in between, which is still duplicate-free.

It is the standard test of the grow-and-shrink window pattern, which is how you answer questions like "the longest stretch of log lines with no repeated request ID" or "the longest run of deploys with no repeated host" in a single pass.