13. Longest Substring Without Repeating Characters
Problem ๐
Given a stringย s, find the length of theย longest substring without repeating characters.
Example:
Input: s = "abcabcbb"
Output: 3
Solution
Solution in C++ using two pointers and a hashmap
The idea is to iteratively find the longest substring without repeating characters by maintaining a sliding window approach. We use two pointers (lowย andย high) to represent the boundaries of the current substring. As we iterate through the string, we update the pointers and adjust the window to accommodate new unique characters and eliminate repeating characters.
Here's the process:
- The map stores characters as keys and their indices as values.
- We still maintain theย
lowย andยhighย pointers and theยmaxSoFarย variable. - We iterate through the string using theย
highย pointer. - If the current character is not in the map or its index is less thanย
left, it means it is a new unique character. Then. we update theยmapย with the character's index and update theยmaxSoFarย if necessary. - If the character is repeating within the current substring, we move theย
lowย pointer to the next position after the last occurrence of the character. - We update the index of the current character in theย
mapย and continue the iteration. - At the end, we return
maxSoFarย as the length of the longest substring without repeating characters.
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> map;
int maxHere = 0, maxSoFar = 0;
for(int low = 0, high = 0; high < s.size(); high++) {
char currChar = s[high];
if(map.contains(currChar) && map[currChar] >= low)
low = map[currChar] + 1;
maxHere = high - low + 1;
maxSoFar = max(maxSoFar, maxHere);
map[currChar] = high;
}
return max(maxHere, maxSoFar);
}
- Time complexity:
(where n is the size of the string) - Space complexity:
(we are storing all the input)