Description
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 the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 10^4sconsists of English letters, digits, symbols, and spaces.
Approach
The idea is to use a sliding window(indicated by the red dashed box) to keep track of the current substring(start as left pointer, i as right pointer). We also use a position map to store the last seen index of each character.
If the character has been seen and is within the current sliding window, we update the start pointer to the next index of the character. We also update the maximum length of the substring found.
Solution
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
// Store the last seen index of each character
let positionMap = {};
// Marks the beginning of the current substring window
let start = 0;
// Keeps track of the longest substring found
let maximumLength = 0;
for (let i = 0; i < s.length; i++) {
const c = s[i];
// If the character has been seen and is within the current window
if (positionMap[c] >= start) {
start = positionMap[c] + 1;
}
positionMap[c] = i;
maximumLength = Math.max(maximumLength, i - start + 1);
}
return maximumLength;
};
Complexity Analysis
Time Complexity
The time complexity is O(2n) because, in the worst case, each character might be visited twice. This simplifies to O(n).
Space Complexity
The space complexity is O(min(n, m)) where n is the length of the string and m is the size of the character set. This is because we store the last seen index of each character. In the worst case, when all characters are unique, the space complexity is O(n).