Problem
Given a string s, return the length of the longest substring that contains no repeated characters.Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "abcabcbb" Output
3 Solution
This solution uses the Sliding Window technique along with a HashSet to maintain a window containing only unique characters.The right pointer expands the window by adding new characters, while the left pointer shrinks the window whenever a duplicate character is encountered.
Each character is added to and removed from the HashSet at most once, ensuring that the window always contains unique characters.
The maximum window size observed during the traversal is the length of the longest substring without repeating characters.
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int left = 0;
int right = 0;
int maxLen = 0;
while (right < s.length()) {
char c = s.charAt(right);
while (set.contains(c)) {
set.remove(s.charAt(left));
left++;
}
set.add(c);
maxLen = Math.max(maxLen, right - left + 1);
right++;
}
return maxLen;
}
Complexity
The algorithm traverses the string using two pointers. Since each character is added to and removed from the HashSet at most once, the overall time complexity isO(n). The extra space complexity is
O(n) in the worst case when all characters in the current window are unique.