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 lengthOfLongestSubstringBruteForce(String s) {
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
Set<Character> seen = new HashSet<>();
for (int j = i; j < s.length(); j++) {
if (seen.contains(s.charAt(j))) break; // hit a repeat — this substring starting at i can't extend further
seen.add(s.charAt(j));
maxLen = Math.max(maxLen, j - i + 1);
}
}
return maxLen;
}Time: O(n^2) · Space: O(min(n, charset size))