Given a string s, return the length of the longest substring (a contiguous block of characters) in which no character appears more than once.
Example 1
Input: s = "abcabcbb"
Output: 3
The substring
"abc" has length 3; any longer block repeats a letter.Example 2
Input: s = "pwwkew"
Output: 3
"wke" works. Note "pwke" is a subsequence, not a substring.Constraints
- 0 <= s.length <= 5 * 10^4
- `s` may contain letters, digits, symbols and spaces
Hints
Frequently asked at: Amazon, Microsoft, Google, Meta, Adobe, Bloomberg
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Checking every substring for repeats is O(n^2) or worse. A sliding window keeps a block with no repeats: extend the right end one character at a time, and when the new character already appears inside the window, move the left end just past its previous position. Remembering each character's last index in a map lets the left end jump directly, so every character is processed once.
Algorithm
- Keep a map
lastfrom character to its latest index,left = 0,best = 0. - For each
rightwith characterc: ifcis inlastandlast[c] >= left, setleft = last[c] + 1. - Set
last[c] = right. - Update
best = max(best, right - left + 1). - Return
best.
Time:
O(n)Space: O(k) where k is the number of distinct charactersInterview tip: The
last[c] >= left check matters: for "abba", when the second a arrives its old index 0 is already outside the window, and jumping back to 1 would be wrong.class Solution: def lengthOfLongestSubstring(self, s: str) -> int: last = {} # char -> latest index left = best = 0 for right, c in enumerate(s): if c in last and last[c] >= left: left = last[c] + 1 # jump past the repeat last[c] = right best = max(best, right - left + 1) return bestCtrl + Enter runs the examples