Find All Anagrams in a String

Share

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.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

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:

Contents

Solution 1 - Using sliding window technique, maintain characters count from String 's' and check against characters count from String 'p'

In this approach, we are going to store characters count from string p in a HashMap, then using Sliding Window technique when the window range from string s is of same length as p's length, check if they are anagrams, if they are then store the starting index into result and move slide towards right.

Implementation steps:
  • Initialize two HashMap's, p_count to store characters count from string p and s_count to store characters count from s.
  • Then, loop through characters of s and store them in s_count, when the window size (number of characters have read from string s) are of same length as string p's length, then check if both HashMap's have same characters and their count, if they are add the starting index of current window to result.
  • When we move slide to next character, i.e. remove window starting indexed character and add next character to s_count, if the character count become zero after decrementing window starting indexed letter we will remove that entry from s_count.
Java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class FindAllAnagrams {

    static List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();

        if(p.length() > s.length()) {
            return result;
        }

        HashMap<Character, Integer> p_count = new HashMap<>();
        HashMap<Character, Integer> s_count = new HashMap<>();

        for(int i=0; i<p.length() -1 ; i++) {
            p_count.merge(p.charAt(i), 1, Integer::sum);
            s_count.merge(s.charAt(i), 1, Integer::sum);
        }
        p_count.merge(p.charAt(p.length()-1), 1, Integer::sum);

        for(int i=p.length() -1; i<s.length(); i++) {
            //add next character to current slide window to make s_count and p_count have same number of characters
            s_count.merge(s.charAt(i), 1, Integer::sum);
            int windowStart = i - p.length() +1;
            if(p_count.equals(s_count)) {
                result.add(windowStart);
            }
            //Now, remove beginning indexed character to move the sliding window
            Integer valAfter = s_count.merge(s.charAt(windowStart), -1, Integer::sum);
            if(valAfter.equals(0)) {
                s_count.remove(s.charAt(windowStart));
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(findAnagrams("cbaebabacd", "abc"));
        System.out.println(findAnagrams("abab", "ab"));
        System.out.println(findAnagrams("baa", "aa"));
        System.out.println(findAnagrams("aaaaaaaaaa", "aaaaaaaaaaaaa"));

    }
}
Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input string s (from the implementation, string s's length should be greater than or equal to string p's length).
Space complexity: O(1), though we are storing characters count into HashMap, as per problem statement input strings will only have lowercase alphabets, so at most we only tracking only 26 characters counts.

Above implementations source code can be found at GitHub link for Java code