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.

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

Solution

Simple approach to check if two strings are anagram or not is to sort both the string and compare it. Here we have given target string as p, We need to check in Source string s if we have Anagrams or not.

Iterate over the Source string and do substring with length as Target string and check if both the strings are Anagrams to each other.

Code

Output

[0, 6]

Complexity Analysis

Let’s say, target String Length as N, and Source String length as K then,

Time complexity: O(KNlogN).
Space Complexity: O(N).

We encourage you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *