Find All Anagrams in a String

Find All Anagrams in a String is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Character Frequency Matching subpattern.

Problem statement

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.

Example 1:

Input: s = "cbaebabacd", p = "abc" Output: [0,6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab" Output: [0,1,2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

- 1 <= s.length, p.length <= 3 104

- s and p consist of lowercase English letters.

Topics and companies

Topics: Hash Table, String, Sliding Window.

Reported in interviews at Amazon, Apple, Bloomberg, Facebook, Google, Microsoft, Snapchat, Uber.

How to practise Find All Anagrams in a String on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Find All Anagrams in a String in the code editor, or read the Find All Anagrams in a String editorial for a worked solution with its approach and complexity analysis.

Where Find All Anagrams in a String sits in the DSA pattern sheet

Problems related to Find All Anagrams in a String

Other problems that use the same Character Frequency Matching and Sliding Window techniques:

Preparing this workspace.