Find All Anagrams in a String - Practice Coding Problems

Find All Anagrams in a String - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "cbaebabacd", p = "ab"

› Output: [1,6]

💡 Note: The anagrams of "ab" in "cbaebabacd" start at indices 1 ("ba") and 6 ("ab"). Both "ba" and "ab" are anagrams of "ab".

Example 2 — Multiple Matches

$ Input: s = "abab", p = "ab"

› Output: [0,2]

💡 Note: Anagrams start at indices 0 ("ab") and 2 ("ab"). Both substrings are exactly the pattern or valid anagrams.

Example 3 — No Matches

$ Input: s = "xyz", p = "ab"

› Output: []

💡 Note: No substring of length 2 in "xyz" can form an anagram of "ab" since the characters don't match.

Constraints

1 ≤ s.length, p.length ≤ 3 × 10⁴
s and p consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String s and pattern p to find anagrams of

Process

Slide window of size |p| and compare character frequencies

Output

Array of starting indices where anagrams are found

Key Takeaway

🎯 Key Insight: Anagrams have identical character frequencies - use sliding window to efficiently compare frequencies in O(n) time

Asked in

f Facebook 35 a Amazon 28 G Google 22 M Microsoft 18

The key insight is that anagrams have identical character frequencies. The optimal sliding window approach maintains frequency counts while sliding through the string, achieving O(n) time complexity. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count Comparison	O(n × m)	O(m)	Compare character frequency maps for each substring
Sliding Window with Frequency Count	O(n + m)	O(1)	Maintain a sliding window with character frequency matching
Brute Force with Sorting	O(n × m × log m)	O(m)	Check every possible substring by sorting characters

Frequency Count Comparison — Algorithm Steps

Step 1: Build frequency map for pattern p
Step 2: For each position in s, build frequency map for substring
Step 3: Compare frequency maps
Step 4: If maps are identical, add index to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Pattern Frequency

Build frequency map for pattern

Substring Frequency

Build frequency map for each substring

Compare Maps

Check if frequencies match exactly

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compareFreq(int freq1[26], int freq2[26]) {
    for (int i = 0; i < 26; i++) {
        if (freq1[i] != freq2[i]) return 0;
    }
    return 1;
}

void getFrequency(char* str, int len, int freq[26]) {
    memset(freq, 0, 26 * sizeof(int));
    for (int i = 0; i < len; i++) {
        freq[str[i] - 'a']++;
    }
}

void solution(char* s, char* p, int* result, int* returnSize) {
    int sLen = strlen(s);
    int pLen = strlen(p);
    int pFreq[26];
    getFrequency(p, pLen, pFreq);
    
    *returnSize = 0;
    
    for (int i = 0; i <= sLen - pLen; i++) {
        int subFreq[26];
        getFrequency(s + i, pLen, subFreq);
        
        if (compareFreq(subFreq, pFreq)) {
            result[(*returnSize)++] = i;
        }
    }
}

int main() {
    char s[30001], p[21];
    fgets(s, sizeof(s), stdin);
    fgets(p, sizeof(p), stdin);
    s[strcspn(s, "\n")] = 0;
    p[strcspn(p, "\n")] = 0;
    
    int result[30000];
    int returnSize;
    solution(s, p, result, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

n positions × m characters to build frequency map

✓ Linear Growth

Space Complexity

O(m)

Space for frequency maps of size at most 26 characters

✓ Linear Space

487.2K Views

High Frequency

~25 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler