Given a string s, find the length of the longest substring without repeating characters.
Example 1
Input: s = "abcabcbb"
Output: 3
Explanation: "abc" is the longest.
Example 2
Input: s = "bbbbb"
Output: 1
Explanation: "b"
Example 3
Input: s = "pwwkew"
Output: 3
Explanation: "wke"
0 <= s.length <= 5*10^4s consists of English letters, digits, symbols and spaces.Sliding window. Expand right; shrink left when a duplicate enters the window.
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int maxLen = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// Shrink window from left if we've seen this char inside the window
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(m,n)) where m=charset size