3. Longest Substring Without Repeating Characters
- Hardness: \(\color{orange}\textsf{Medium}\)
- Ralated Topics:
Hash Table、String、Sliding Window
一、題目
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.
二、分析
- 這題是
Sliding Window的應用，創建一個 sliding window，右指標滑動的條件為，window 中無重複的字元，當出現重複字元時，則滑動左指標。 - 時間複雜度為 \(O(n)\)，空間複雜度為 \(O(1)\)。
- 空間複雜度為 \(O(k)\)，k 為字元的個數，最多為 128 個(題目限制字元為 letters, digits, symbols and spaces)，故\(O(k)=O(128)=O(1)\)
三、解題
1. Sliding Window
- Time complexity: \(O(n)\)
- Space complexity: \(O(1)\)
int lengthOfLongestSubstring(string s) {
int cnt[128] = {0};
int left = 0, right = 0;
int res = 0;
while (right < s.length()) {
char c = s[right++];
while (cnt[c]) { // 若 window 中已有該字元，則滑動左指標
char d = s[left]++;
cnt[d]--; // 將 window 中，左指標的字元數減 1
}
res = max(res, right - left); // 比較當前的長度
cnt[c]++; // 將 window 中，右指標的字元數加 1
}
return res;
}