# 438 Find All Anagrams in a String

## 438. [Find All Anagrams in a String](https://leetcode.com/problems/find-all-anagrams-in-a-string/description/)

## 1. Question

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

## 2. Implementation

**(1) Two Pointers + Hash**

```java
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();

        if (s == null || s.length() == 0 || p == null || p.length() == 0) {
            return res;
        }

        int start = 0, end = 0, count = p.length();
        int[] map = new int[256];

        for (char c : p.toCharArray()) {
            ++map[c];
        }

        while (end < s.length()) {
            if (map[s.charAt(end)] >= 1) {
                --count;
            }
            --map[s.charAt(end)];
            ++end;

            while (end - start - 1 == p.length()) {
                if (map[s.charAt(start)] >= 0) {
                    ++count;
                }
                ++map[s.charAt(start)];
                ++start;
            }

            if (count == 0) {
                res.add(start);
            }
        }
        return res;
    }
}
```

## 3. Time & Space Complexity

**Two Pointers + Hash:** 时间复杂度O(n), 空间复杂度O(n)