3. Longest Substring Without Repeating Characters
1. Description
Given a string s, find the length of the longest substring without duplicate characters.
2. Example
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.
3. Constraints
- 0 <= s.length <= 5 * 10$^4$
- s consists of English letters, digits, symbols and spaces.
4. Solutions
Sliding Window
n = str.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
int lengthOfLongestSubstring(const string &str) {
const int n = str.size();
int max_length = 0;
array<int, 128> count{};
for (int left = 0, right = 0; right < n; ++right) {
++count[str[right]];
while (count[str[right]] > 1) {
--count[str[left]];
++left;
}
max_length = max(max_length, right - left + 1);
}
return max_length;
}
};
Optimized Sliding Window
n = str.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
int lengthOfLongestSubstring(const string &str) {
const int n = str.size();
array<int, 128> prev_index;
prev_index.fill(-1);
int max_length = 0;
for (int left = 0, right = 0; right < n; ++right) {
left = max(left, prev_index[str[right]] + 1);
max_length = max(max_length, right - left + 1);
prev_index[str[right]] = right;
}
return max_length;
}
};