algoadvance

Leetcode 438. Find All Anagrams in a String

Problem Statement

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:

Clarifying Questions

  1. Can s and p be empty?
    • No, given the constraints both s and p will have at least one character.
  2. Are special characters or spaces allowed in s or p?
    • No, the strings consist only of lowercase English letters.
  3. Can s be smaller than p?
    • No, it’s specified that s and p both have lengths between 1 and 30000, and it’s implicitly given that we will only perform operations when looking for anagrams where it makes sense (i.e., s.length should be greater or equal top.length).

Strategy

To find all anagrams of the string p in s, we’ll leverage a sliding window technique with a frequency counter. The idea is to maintain a window of length equal to p and slide it across s, updating the frequency counts of characters and checking if they match the character frequency of p.

  1. Initialize Frequency Arrays:
    • Create frequency arrays (or hashmaps) for p and the current window in s.
  2. Setup Initial Window:
    • Populate the frequency array for the initial window of length p from the start of s.
  3. Slide the Window:
    • Slide the window one character at a time.
    • Update the frequency arrays by removing the count of the character that’s left behind and adding the new character that comes into the window.
  4. Check for Anagrams:
    • After each slide, compare the frequency arrays: if they are equal, the current starting index is an anagram’s starting point.
  5. Return Indices:
    • Collect and return all starting indices where the frequency arrays matched.

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class AnagramFinder {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if(s.length() < p.length()) return result;
        
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        
        // Count frequency of each character in p
        for(char ch : p.toCharArray()) {
            pCount[ch - 'a']++;
        }
        
        // Populate the initial window
        for(int i = 0; i < p.length(); i++) {
            sCount[s.charAt(i) - 'a']++;
        }
        
        // Check if initial window matches
        if(Arrays.equals(sCount, pCount)) {
            result.add(0);
        }
        
        // Slide the window across `s`
        for(int i = p.length(); i < s.length(); i++) {
            // add new character to the window
            sCount[s.charAt(i) - 'a']++;
            // remove the old character from the window
            sCount[s.charAt(i - p.length()) - 'a']--;
            
            // check if matching
            if(Arrays.equals(sCount, pCount)) {
                result.add(i - p.length() + 1);
            }
        }
        
        return result;
    }
}

Time Complexity

This approach efficiently finds all starting indices of anagrams of p in s by using sliding window and constant-time character frequency comparison.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI