438. Find All Anagrams in a String

Medium LeetCode

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

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

Constraints:

• 1 <= s.length, p.length <= 3 * 10^4
• s and p consist of lowercase English letters only.

How to solve the problem

• Sliding Window with Sorting O(n·m log m)

class Solution:
    def findAnagrams(self, s:str, p:str) -> List[int]:
        left = 0
        p_sorted = sorted(p)
        result = []
        for right in range(len(p)-1, len(s)):
            if sorted(s[left:right+1]) == p_sorted:
                result.append(left)
            left += 1
        return result

• Sliding Window with Counter O(n * m)

class Solution:
    def findAnagrams(self, s:str, p:str) -> List[int]:
        left = 0
        p_count = Counter(p)
        result = []
        for right in range(len(p)-1, len(s)):
            if Counter(s[left:right+1]) == p_count:
                result.append(left)
            left += 1
        return result

• Sliding Window with Counter Hashmap O(n)

python

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        left = 0
        result = []
        p_count = Counter(p)
        window = Counter(s[: len(p)])
        for right in range(len(p), len(s)):
            if window == p_count:
                result.append(left)
            window[s[left]] -= 1
            window[s[right]] += 1
            left += 1
            if window[s[left]] == 0:
                del window[s[left]]
        if window == p_count:
            result.append(left)
        return result

Java

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (p.length() > s.length()) return new ArrayList<>();

        // Count frequency of p
        HashMap<Character, Integer> p_count = new HashMap<>();
        for (char c : p.toCharArray()) {
            p_count.put(c, p_count.getOrDefault(c, 0) + 1);
        }

        //Initialize frquency of window
        HashMap<Character, Integer> window = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            char c = s.charAt(i);
            window.put(c, window.getOrDefault(c, 0) + 1);
        }

        int left = 0;
        List<Integer> result = new ArrayList<>();
        for (int right = p.length(); right < s.length(); right++) {
            if (window.equals(p_count)) {
                result.add(left);
            }

            // Add new char at right
            char inChar = s.charAt(right);
            window.put(inChar, window.getOrDefault(inChar, 0) + 1);

            // Remove old char at left
            char outChar = s.charAt(left);
            window.put(outChar, window.get(outChar) - 1);
            if (window.get(outChar) == 0) {
                window.remove(outChar);
            }
            left++;
        }
        // Check the last window
        if (window.equals(p_count)) {
            result.add(left);
        }
        return result;
    }
}

Complexity

• Time Complexity: O(n) - Where n is the length of string s. We traverse the string once with the sliding window.
• Space Complexity: O(k) - Where k is the number of unique characters in string p. The hash map stores at most k characters.