What is the primary technique used to solve 'Find All Anagrams in a String'?

The problem is solved using the sliding window technique combined with a hash table to track character frequencies.

How does the sliding window technique help in solving this problem?

The sliding window technique allows you to efficiently update the window of characters in s and check for anagrams in linear time without recalculating frequencies from scratch.

Can this problem be solved in less than O(n) time complexity?

No, achieving O(n) time complexity is the optimal solution for this problem. Any approach slower than O(n) would not be efficient enough for large inputs.

Why is a hash table used in 'Find All Anagrams in a String'?

A hash table is used to store the character frequencies of both the target string p and the current sliding window in s, enabling quick comparison and updates as the window slides.

What happens if the length of s is smaller than p in 'Find All Anagrams in a String'?

If the length of s is smaller than p, there are no possible anagrams, and the function should return an empty array.

#438

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

找到字符串中所有字母异位词

给定两个字符串 s 和 p ，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。示例 1: 输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。起始…

哈希表字符串滑动窗口

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

1 <= s.length, p.length <= 3 * 10⁴
s 和 p 仅包含小写字母

lightbulb

解题思路

方法一：滑动窗口

我们不妨设字符串 $s$ 的长度为 $m$ ，字符串 $p$ 的长度为 $n$ 。

如果 $m \lt n$ ，那么 $s$ 中不可能存在任何一个子串同 $p$ 为异位词，返回空列表即可。

当 $m \ge n$ 时，我们可以使用一个固定长度为 $n$ 的滑动窗口来维护 $s$ 的子串。为了判断子串是否为 $p$ 的异位词，我们可以用一个固定长度为 $26$ 的数组 $cnt1$ 记录 $p$ 中每个字母的出现次数，再用另一个数组 $cnt2$ 记录当前滑动窗口中每个字母的出现次数，如果这两个数组相同，那么当前滑动窗口的子串就是 $p$ 的异位词，我们记录下起始位置。

时间复杂度 $O(m \times C)$ ，空间复杂度 $O(C)$ 。其中 $m$ 是字符串 $s$ 的长度；而 $C$ 是字符集大小，在本题中字符集为所有小写字母，所以 $C = 26$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        m, n = len(s), len(p)
        ans = []
        if m < n:
            return ans
        cnt1 = Counter(p)
        cnt2 = Counter(s[: n - 1])
        for i in range(n - 1, m):
            cnt2[s[i]] += 1
            if cnt1 == cnt2:
                ans.append(i - n + 1)
            cnt2[s[i - n + 1]] -= 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate understanding of sliding window technique and hash table usage.
question_mark
Look for correct handling of window updates and frequency comparison.
question_mark
The candidate should be able to explain the time and space complexity effectively.

warning

常见陷阱

外企场景

error
Incorrectly resizing the window, leading to missed or false positives for anagrams.
error
Not updating the hash table correctly when characters enter and exit the window.
error
Failing to recognize the importance of tracking frequencies in constant time to achieve linear time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the input strings contain uppercase letters as well? Adapt the hash table to handle both cases.
arrow_right_alt
How would you handle edge cases where s is shorter than p?
arrow_right_alt
Can the solution be optimized further for a scenario with a large number of unique characters?

help

常见问题

外企场景

继续练习

#424 替换后的最长重复字符 #395 至少有 K 个重复字符的最长子串 #567 字符串的排列