Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Constraints:
- 1 <= s.length <= 10^5
- s consists of English letters, digits, symbols and spaces.
Examples:
Input: abcabcbb
Output: 3
Explanation: The answer is "abc", with the length of 3.
Input: bbbbb
Output: 1
Explanation: The answer is "b", with the length of 1.
Input: pwwkew
Output: 3
Explanation: The answer is "wke", with the length of 3.
Solutions
Sliding Window
We use a sliding window approach to solve this problem. We maintain a left pointer and a right pointer, and a map to store the characters we have seen so far and their indices. We move the right pointer to the right and update the map. If we encounter a character that is already in the map, we move the left pointer to the right of the previous occurrence of the character. We keep track of the maximum length of the substring without repeating characters.
public
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0;
int maxLength = 0;
Map<Character, Integer> charIndexMap = new HashMap<>();
for (int right = 0;
right < s.length();
right++) {
if (charIndexMap.containsKey(s.charAt(right))) {
left = Math.max(left, charIndexMap.get(s.charAt(right)) + 1);
}
charIndexMap.put(s.charAt(right), right);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}Follow-up:
What if we need to find the longest substring with at most k repeating characters?
