🔗 🟡 567. Permutation in String

tags: `字串(String)`, `雙指標(Two Pointers)`, `滑動窗口(Sliding Window)`, `雜湊表(Hash Table)`

題意

給定兩個字串 $s_1$ 和 $s_2$ ，如果 $s_2$ 包含 $s_1$ 的一個排列，則返回 $true$ ，否則返回 $false$ 。

換句話說，如果 $s_1$ 的一個排列是 $s_2$ 的子字串，則返回 $true$ 。

約束條件

$1 \leq s_1.length, s_2.length \leq 10^4$
$s_1$ 和 $s_2$ 只包含小寫英文字母。

思路：滑動窗口(Sliding Window) + 雜湊表(Hash Table)

假設 $t$ 是 $s_1$ 的一個排列，那麼 $t$ 的長度必定與 $s_1$ 的長度相同，且 $t$ 中每個字元的出現次數也與 $s_1$ 中每個字元的出現次數相同。

為了檢查 $s_2$ 中是否存在一個子陣列滿足此性質，我們可以使用雜湊表(Hash Table) $cnt$ 來記錄 $s_1$ 中每個字元的出現次數，並在 $s_2$ 上使用滑動窗口來檢查。

使用兩個指針 $left$ 和 $right$ 表示一個窗口的左右端點，初始時都指向 $0$ 。令 $right$ 指針向右移動，每次移動時，將 $rc = s_2[right]$ 對應的計數器減 $1$ ，即 $cnt[rc] -= 1$ 。
如果 $cnt[rc] < 0$ ，則表示 $rc$ 在窗口內中出現的次數超過了 $s_1$ 中該字元的出現次數，此時需要將 $left$ 指針向右移動，並對 $lc = s_2[left]$ 對應的計數器加 $1$ ，直到 $cnt[rc] \geq 0$ 為止。
最後，如果 $right - left + 1$ 等於 $s_1$ 的長度，則表示 $s_2$ 中存在一個子陣列滿足此性質，返回 $true$
如果遍歷完 $s_2$ 都沒有找到符合條件的窗口，則返回 $false$ 。

此外，由於 $s_1$ 和 $s_2$ 只包含小寫英文字母，因此我們也可以使用長度為 $26$ 的陣列來記錄每個字元的出現次數，可以參考 C++ 的實現。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 是 $s_2$ 的長度。
空間複雜度： $\mathcal{O}(1)$ ，由於雜湊表的大小固定為 $26$ ，因此空間需求是常數級別的。

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        cnt = Counter(s1) # 每個字元還需要的數量
        left = 0
        for right, ch in enumerate(s2):
            cnt[ch] -= 1
            while cnt[ch] < 0: # 這個字元的數量太多了
                cnt[s2[left]] += 1
                left += 1
            if right - left + 1 == len(s1): # 窗口大小等於 s1 的長度
                return True
        return False

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        if (m > n) return false;
        vector<int> cnt(26); // 每個字元還需要的數量
        for (char ch : s1) cnt[ch - 'a']++;
        int left = 0;
        for (int right = 0; right < n; right++) {
            int idx = s2[right] - 'a';
            cnt[idx]--;
            while (cnt[idx] < 0) { // 這個字元的數量太多了
                cnt[s2[left] - 'a']++;
                left++;
            }
            if (right - left + 1 == m) return true; // 窗口大小等於 s1 的長度
        }
        return false;
    }
};