Longest Substring Without Repeating Characters
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
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
- Keep a hash map
last_index(character → its most recent index), aleftpointer starting at 0, and a runningbest. - For each position
rightin the string, with characterch = s[right]:- If
chwas seen before and that earlier occurrence is still inside the current window (its index is>= left), moveleftto just past it. - Record
ch's current position inlast_index. - Update
bestif the current window's length (right - left + 1) is larger.
- If
- 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")) # 3RecapThe 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
lefton *any* previous sighting of a character, not just one still inside the window, can moveleftbackward and break the window — always check the stored index is>= leftfirst
Interview follow-ups
What if you needed to return the actual longest substring, not just its length?
Track the
leftandrightvalues at the momentbestis updated (or just re-slices[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, andbest— 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 behindleft) 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.
