Find All Anagrams in a String: Amazon

Problem

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s. Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100. The order of output does not matter.

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”.

https://leetcode.com/problems/find-all-anagrams-in-a-string/

Solution

Naive Solution

The time complexity of naive solution is O(N*M) time. N and N are the length of the input strings s and p. we check all string that starts from each index in s. By repeating M times this handling, we can solve it.

And it is good to user integer of array in order to keep the count of character appearance. In input string is ASCII case, the maximum index will be 256.

Optimize Solution

This algorithm takes O(N) time, so this code is faster than naive solution. By control left and right index like sliding window, we can check all anagrams in O(N) time.

The condition of anagram is the following.

• two strings are same length.
• count of appearance of each character are same.

In above code, if (count == 0) { means that all characters of p are appeared in s. So, we count up the anagram in this condition.