438 Find All Anagrams in a String

438. Find All Anagrams in a String

1. Question

Given a strings and a non-empty stringp, find all the start indices of p's anagrams ins.

Strings consists of lowercase English letters only and the length of both stringssandpwill 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

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)