題目資訊

題目編號: 1100
題目連結: Find K-Length Substrings With No Repeated Characters
主題: Hash Table, String, Sliding Window

題目敘述

給定一個字串 $s$ 和一個整數 $k$，返回字串 $s$ 中長度為 $k$ 且不含重複字元的子字串數量。

範例 1:

輸入： $s = “havefunonleetcode”$, $k = 5$
輸出： 6
解釋： 有 6 個子字串分別是：‘havef’, ‘avefu’, ‘vefun’, ’efuno’, ’etcod’, ’tcode’。

範例 2:

輸入： $s = “home”$, $k = 5$
輸出： 0
解釋： 注意 $k$ 可以大於 $s$ 的長度。在這種情況下，無法找到任何子字串。

約束條件：

$1 \leq s.\text{length} \leq 10^4$
$s$ 由小寫英文字母組成。
$1 \leq k \leq 10^4$

直覺

這個問題要求我們計算字串 $s$ 中長度為 $k$ 的所有子字串，其特點是不包含重複的字元。我們需要有效地處理子字串以確保字元的唯一性。使用滑動窗口方法可以讓我們在遍歷字串的過程中高效地管理和更新窗口。滑動窗口技術利用數組或字串中連續段的特性，能夠在重疊和推進是關鍵的情況下達到最佳效果。

解法

這個算法採用了滑動窗口範式，使用兩個指針來定義當前窗口的開始（left）和結束（right），這代表了字串 $s$ 的一個子字串。下面是具體步驟：

初始化：
- 使用大小為 26 的布林向量 is_char_used（對應小寫英文字母的總數）初始化為 false，用來跟踪當前子字串中每個字元的使用情況。
- 將 left、right 和 result_count 初始化為零。left 和 right 指針用來管理滑動窗口的邊界，而 result_count 用來跟踪找到的有效子字串的數量。
窗口擴展：
- 使用 right 指針遍歷字串，直到其小於字串的長度。每次迭代時，檢查在當前窗口中 $s[\text{right}]$ 這個字元是否已經被使用。
處理字元重複：
- 如果 $s[\text{right}]$ 這個字元已經被標記為使用過，則增量 left 指針以從左側縮小窗口，直到該字元是唯一的。在這個過程中，將 is_char_used 中的 $s[\text{left}]$ 字元標記為未使用。
標記字元使用：
- 將 $s[\text{right}]$ 這個字元標記為使用過，通過將 is_char_used 中對應的索引設置為 true。
窗口大小驗證：
- 檢查窗口大小是否至少為 $k$。如果是，則表示一個有效的子字串，並增量 result_count。
返回結果：
- 當循環結束時，返回 result_count，這包含找到的有效子字串數量。

這一過程確保每個字元在任何潛在的 $k$ 長子字串中只被考慮一次，通過使用滑動窗口和跟踪機制高效滿足了不重複的要求。

程式碼

C++

class Solution {
public:
    int numKLenSubstrNoRepeats(string s, int k) {
        // 一個向量用來追蹤已使用的字符，初始化為26個false值
        vector<bool> is_char_used(26, false);
        
        int left = 0;  // 滑動視窗的起始索引
        int right = 0; // 滑動視窗的結束索引
        int result_count = 0; // 計算有效子字串的數量
        int string_length = s.size(); // 輸入字串的長度
        
        // 當視窗擴展時，使用右索引迭代每個字符
        for (; right < string_length; right++) {
            // 如果當前字符已在當前視窗中使用過
            if (is_char_used[s[right] - 'a']) {
                // 移動左指標直到右指標的字符不重複
                do { 
                    is_char_used[s[left] - 'a'] = false; 
                } while (s[left++] != s[right]);
            }
            
            // 標記當前字符已被使用
            is_char_used[s[right] - 'a'] = true;
            
            // 如果視窗大小至少為k，則增加結果計數
            if (right - left + 1 >= k) {
                result_count++;
            }
        }
        
        return result_count; // 返回找到的有效子字串數量
    }
};

Python

class Solution:
    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
        # 用於追蹤使用過的字符的列表，初始化為26個False值
        is_char_used = [False] * 26
        
        left = 0  # 滑動窗口的起始索引
        right = 0 # 滑動窗口的結束索引
        result_count = 0 # 用於計算有效子字串的數量
        string_length = len(s) # 輸入字串的長度
        
        # 使用right索引遍歷每個字符，隨著窗口擴展
        while right < string_length:
            # 如果目前字符已經在當前窗口中使用過
            if is_char_used[ord(s[right]) - ord('a')]:
                # 向右移動left索引，直到right位置的字符不重複
                while s[left] != s[right]:
                    is_char_used[ord(s[left]) - ord('a')] = False
                    left += 1
                left += 1
            
            # 標記當前字符為已使用
            is_char_used[ord(s[right]) - ord('a')] = True
            
            # 如果窗口大小至少為k，則計算結果數量加1
            if right - left + 1 >= k:
                result_count += 1
            
            right += 1
        
        return result_count # 返回找到的有效子字串數量

複雜度分析

時間複雜度: $O(n)$
該演算法採用了滑動窗口的方法遍歷字串。right 指標恰好遍歷字串中的每個字元一次，因此複雜度為 $O(n)$，其中 $n$ 是字串 $s$ 的長度。儘管有一個內部循環移動 left 指標，但每個字元最多被處理兩次（一次加入窗口，一次被移除），確保該循環內的總操作量仍然是 $O(n)$。
空間複雜度: $O(1)$
該演算法使用一個固定長度為 26 的向量 is_char_used 來追蹤每個小寫英文字母的使用情況。這個空間需求不隨輸入尺寸變化，因此空間複雜度為 $O(1)$。 left、right、result_count 和 string_length 的整數變數也佔用一個恆定的空間量。

CS Note
En

Leetcode 1100. Find K-Length Substrings With No Repeated Characters

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析