438. Find All Anagrams in a String

Medium

Description

給定字串 s 和字串 p，找出 s 中所有 p 的 anagram（字母異位詞）的起始索引。回傳索引列表，順序不限。

Example:

Input: s = “cbaebabacd”, p = “abc” Output: [0, 6] （“cba” 和 “bac” 都是 “abc” 的 anagram）

Intuition#

核心思路：固定大小的滑動窗口（大小等於 p 的長度），維護窗口內的字元頻率，當頻率與 p 完全匹配時記錄起始位置。

窗口大小固定為 p.length，每次右移一格，加入新字元、移除舊字元
用頻率陣列（26 個字母）比較窗口與 p 的字元分布
優化：維護 matches 計數器，追蹤有多少個字母的頻率已匹配，避免每次比較整個陣列

Approaches#

1: Sliding Window + Array Compare#

概念: 維護窗口的頻率陣列，每次滑動後比較兩個頻率陣列
時間複雜度: O(n * 26) - 每次滑動比較 26 個字母（n 為 s 的長度）
空間複雜度: O(1) - 固定大小的頻率陣列

class Solution {
    fun findAnagrams(s: String, p: String): List<Int> {
        val result = mutableListOf<Int>()
        if (s.length < p.length) return result

        val pCount = IntArray(26)
        val sCount = IntArray(26)

        for (c in p) pCount[c - 'a']++
        for (i in 0 until p.length) sCount[s[i] - 'a']++

        if (pCount.contentEquals(sCount)) result.add(0)

        for (i in p.length until s.length) {
            sCount[s[i] - 'a']++
            sCount[s[i - p.length] - 'a']--
            if (pCount.contentEquals(sCount)) result.add(i - p.length + 1)
        }
        return result
    }
}

⭐2: Sliding Window + Matches Counter#

概念: 維護 matches 計數器，記錄 26 個字母中有幾個頻率已匹配。滑動窗口時只更新受影響的字母，當 matches == 26 時記錄結果
時間複雜度: O(n) - 每次滑動只做 O(1) 操作
空間複雜度: O(1) - 固定大小的頻率陣列

class Solution {
    fun findAnagrams(s: String, p: String): List<Int> {
        val result = mutableListOf<Int>()
        if (s.length < p.length) return result

        val pCount = IntArray(26)
        val sCount = IntArray(26)
        for (c in p) pCount[c - 'a']++

        var matches = 0

        for (i in 0 until 26) {
            // 初始化：計算第一個窗口
        }

        for (i in 0 until p.length) {
            sCount[s[i] - 'a']++
        }
        for (i in 0 until 26) {
            if (sCount[i] == pCount[i]) matches++
        }
        if (matches == 26) result.add(0)

        for (i in p.length until s.length) {
            // 加入右邊新字元
            val addIdx = s[i] - 'a'
            sCount[addIdx]++
            if (sCount[addIdx] == pCount[addIdx]) matches++
            else if (sCount[addIdx] == pCount[addIdx] + 1) matches--

            // 移除左邊舊字元
            val removeIdx = s[i - p.length] - 'a'
            sCount[removeIdx]--
            if (sCount[removeIdx] == pCount[removeIdx]) matches++
            else if (sCount[removeIdx] == pCount[removeIdx] - 1) matches--

            if (matches == 26) result.add(i - p.length + 1)
        }
        return result
    }
}

🔑 Takeaways#

Pattern: 固定窗口的 anagram 偵測 -> Sliding Window + 頻率比較
關鍵技巧: matches 計數器避免每次比較整個陣列，將每次滑動降到 O(1)；此技巧可推廣到所有固定窗口的字元比較問題