### Problem Statement

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

**Problem link**

### Video Tutorial

You can find the detailed video tutorial here### Thought Process

This looks like a string pattern matching problem, we might start go down the KMP or Rabin Karp route (calculate string hash value). However, the unique requirement is they need to be anagrams. We already know several way to compare if two words are anagrams. Sort, bucketize it. Assuming the longer string length is N, the shorter pattern string length is M, if we do it in brute force way, i.e., for each M length substring in N, we check if they are anagrams, it is O(N*M) assuming we have to repopulate all the maps. Obviously we can optimize this by keeping a sliding window only insert and delete one character at a time. That way, it is only O(N*256), still O(N). (note, 256 is the ASCII char length since every time we need to compare if two ASCII char maps are the same or not)It is also a good problem to have a pattern on coding for two pointers (sliding) window problem.

- Initialize the two maps
- Keep a start and end pointer, move one at a time
- Don't forget to compare the last element

### Solutions

#### Sliding Window using Two Pointers

#### Time Complexity:O(N), len(s) is N, len(p) is M. We only loop through s once, each time we compare anagrams with a constant 256 loop, thus O(256*N) = O(N)

Space Complexity: O(N)

## No comments:

## Post a Comment