3. Longest Substring Without Repeating Characters
Tags: ‘Hash Table’, ‘Two Pointers’, ‘String’, ‘Sliding Window’
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew" Output: 3 Explanation: The answer is"wke", with the length of 3. Note that the answer must be a substring,"pwke"is a subsequence and not a substring.
Solution 1 Sliding Window
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int result = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j));
j++;
result = Math.max(result, j - i);
} else {
set.remove(s.charAt(i));
i++;
}
}
return result;
}
// Optimized Sliding Window using HashMap
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}