Given a string s, find the length of the longest substring without repeating characters.
Example 1
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with length 3.
Example 2
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with length 1.
Example 3
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with length 3. Note "pwke" is a subsequence, not a substring.
0 <= s.length <= 5 * 10^4s consists of English letters, digits, symbols and spacesThink in terms of a window [left, right] that only ever grows or shrinks from one side.
What data structure lets you check 'have I seen this character in my current window' in O(1)?
When you hit a repeat, you don't need to shrink one character at a time — jump left directly past the previous occurrence.
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int maxLen = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
left = lastSeen.get(c) + 1;
}
lastSeen.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Time: O(n) · Space: O(min(n, charset size))