Given a string s, find the length of the longest substring without duplicate characters.
Example 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Note that"bca"and"cab"are also correct answers.
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 * 104sconsists of English letters, digits, symbols and spaces.
Approach 01: Sliding Window
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector charMap(128, -1);
int left = 0, maxLength = 0;
for (int right = 0; right < s.length(); right++) {
if (charMap[s[right]] >= left) {
left = charMap[s[right]] + 1;
}
charMap[s[right]] = right;
maxLength = max(maxLength, right - left + 1);
}
return maxLength;
}
};
Time Complexity:
- O(n): We iterate through the string of length
nonce. Each character is visited byrightpointer once.
Space Complexity:
- O(min(m, n)): We use a constant space (128 for ASCII) to store the latest index of each character.
mis the size of the charset.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
charMap = {}
left = 0
maxLength = 0
for right in range(len(s)):
if s[right] in charMap and charMap[s[right]] >= left:
left = charMap[s[right]] + 1
charMap[s[right]] = right
maxLength = max(maxLength, right - left + 1)
return maxLength
Time Complexity:
- O(n): We iterate through the string once. Each character is visited by
rightpointer once.
Space Complexity:
- O(min(m, n)): We use a dictionary to store the latest index of each character.
class Solution {
public int lengthOfLongestSubstring(String s) {
Integer[] charMap = new Integer[128];
int left = 0, maxLength = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (charMap[c] != null && charMap[c] >= left) {
left = charMap[c] + 1;
}
charMap[c] = right;
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}
Time Complexity:
- O(n): We iterate through the string once. Each character is visited by
rightpointer once.
Space Complexity:
- O(min(m, n)): We use an array of size 128 to store the latest index of each character.