567. Permutation in String

Medium
Description

給定兩個字串 s1 和 s2，判斷 s2 是否包含 s1 的排列（permutation）。換句話說，判斷 s2 的某個子字串是否是 s1 的 anagram。

Example:

Input: s1 = “ab”, s2 = “eidbaooo” Output: true

Intuition#

用固定長度為 s1.length 的滑動視窗在 s2 上滑動，比較視窗內的字元頻率是否與 s1 相同。

  • 排列的本質：兩個字串的字元頻率完全相同
  • 用固定大小的視窗在 s2 上滑動，每次檢查視窗內的字元頻率
  • 可以用 matches 計數器追蹤有多少個字元的頻率已經匹配，避免每次比較整個頻率陣列

Approaches#

1: Sorting#

  • 概念: 對 s1 排序，再對 s2 的每個長度為 s1.length 的子字串排序比較
  • 時間複雜度: O(n * m log m)，n 為 s2 長度，m 為 s1 長度
  • 空間複雜度: O(m)
Sorting 程式碼
class Solution {
    fun checkInclusion(s1: String, s2: String): Boolean {
        if (s1.length > s2.length) return false
        val sorted1 = s1.toCharArray().sorted()
        for (i in 0..s2.length - s1.length) {
            val sub = s2.substring(i, i + s1.length).toCharArray().sorted()
            if (sub == sorted1) return true
        }
        return false
    }
}

⭐2: Sliding Window + Matches Counter#

  • 概念: 維護固定長度視窗，用 matches 計數器追蹤已匹配的字元種類數
  • 時間複雜度: O(n)，n 為 s2 長度
  • 空間複雜度: O(1)（固定 26 個字母）
class Solution {
    fun checkInclusion(s1: String, s2: String): Boolean {
        if (s1.length > s2.length) return false
        val s1Count = IntArray(26)
        val s2Count = IntArray(26)
        for (i in s1.indices) {
            s1Count[s1[i] - 'a']++
            s2Count[s2[i] - 'a']++
        }
        var matches = 0
        for (i in 0 until 26) {
            if (s1Count[i] == s2Count[i]) matches++
        }
        for (right in s1.length until s2.length) {
            if (matches == 26) return true
            // 加入右邊字元
            val rIdx = s2[right] - 'a'
            s2Count[rIdx]++
            if (s2Count[rIdx] == s1Count[rIdx]) matches++
            else if (s2Count[rIdx] == s1Count[rIdx] + 1) matches--
            // 移除左邊字元
            val lIdx = s2[right - s1.length] - 'a'
            s2Count[lIdx]--
            if (s2Count[lIdx] == s1Count[lIdx]) matches++
            else if (s2Count[lIdx] == s1Count[lIdx] - 1) matches--
        }
        return matches == 26
    }
}

🔑 Takeaways#

  • Pattern: 固定長度滑動視窗 + 頻率匹配
  • 關鍵技巧: 用 matches 計數器追蹤匹配的字元種類數，避免每次 O(26) 的比較，是 anagram 類問題的經典最佳化