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^4
  • s consists of English letters, digits, symbols and spaces.

二、分析

sliding window

  • 這題是 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;
}

回目錄 Catalog