DSA problem
Find All Anagrams in a String
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Every anagram of p has exactly the same length as p, so we only ever examine substrings of s whose length equals len(p). Two strings are anagrams if and only if they have identical character-frequency counts. By sliding a window of fixed width len(p) across s and maintaining a running frequency table, each window can be checked in constant time.
Examples
Example 1
Input:
s = "cbaebabacd", p = "abc"Output:
[0,6]Explanation: The substring starting at index 0 is "cba", an anagram of "abc". The substring starting at index 6 is "bac", also an anagram of "abc".
Example 2
Input:
s = "abab", p = "ab"Output:
[0,1,2]Explanation: The substrings "ab" (index 0), "ba" (index 1), and "ab" (index 2) are all anagrams of "ab".
Example 3
Input:
s = "aa", p = "bb"Output:
[]Explanation: There is no substring of "aa" that is an anagram of "bb".
Constraints
- 1 <= s.length, p.length <= 3 * 10^4
- s and p consist of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.