Find All Anagrams in a String

97.9k
0

Given two strings s and p, both containing lowercase English letters, return the starting indices of all substrings of s that are anagrams of p.

Every considered substring must have the same length as p. The indices may be returned in any order.

Example 1

Input: s = "cbaebabacd", p = "abc"

Output: [0, 6]

Explanation: The substring starting at index 0 is "cba", which contains the same character frequencies as "abc". The substring starting at index 6 is "bac", which is also an anagram of "abc".

Example 2

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

Output: [0, 1, 2]

Explanation: The substrings "ab", "ba", and "ab" begin at indices 0, 1, and 2. Every substring contains one 'a' and one 'b'.

Brute Force Approach

Every anagram contains identical characters with identical frequencies. Sorting places those characters in a fixed order, so two strings are anagrams when both sorted forms match.

Every candidate substring must have length M, where M represents the length of p. Sorting p once creates the target form. Sorting every length-M substring of s and comparing both forms checks every possible answer directly.

Algorithm

  • Store the lengths of s and p as N and M.

  • Return an empty result when M > N, because no substring of s can contain M characters.

  • Create sortedP as a sorted copy of p, preserving the original target string.

  • Traverse every valid starting index from 0 to N - M.

  • Extract the length-M substring beginning at the current index.

  • Sort the extracted substring to create a canonical character order.

  • Append the current starting index when the sorted substring matches sortedP.

  • Return the result after checking every possible window.

Dry Run

fa

fa

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Finds all anagram starts by sorting
every candidate window. */
vector<int> findAnagrams(string s, string p) {
vector<int> result;
int n = s.length();
int m = p.length();
// Stop when no window can match the target length.
if (m > n) {
return result;
}
// Build one canonical form for the target string.
string sortedP = p;
sort(sortedP.begin(), sortedP.end());
// Generate and validate every window of length m.
for (int start = 0; start + m <= n; start++) {
string window = s.substr(start, m);
// Sort the current candidate substring.
sort(window.begin(), window.end());
// Record a window with the same sorted form.
if (window == sortedP) {
result.push_back(start);
}
}
return result;
}
};
// Driver code to execute the solution.
int main() {
string s = "cbaebabacd";
string p = "abc";
Solution solution;
vector<int> answer =
solution.findAnagrams(s, p);
// Print the resulting indices.
cout << "[";
for (
int index = 0;
index < (int)answer.size();
index++
) {
cout << answer[index];
if (index + 1 < (int)answer.size()) {
cout << ", ";
}
}
cout << "]" << endl;
return 0;
}

Complexity Analysis

Time Complexity: O((N - M + 1) × M log M), where N represents the length of s and M represents the length of p. Every candidate substring contains M characters and is sorted independently.

Space Complexity: O(M) auxiliary space, excluding the returned indices. A temporary substring and the corresponding sortable character storage can contain M characters. A result containing A matching indices requires O(A) output space.

Better Approach

Sorting every candidate substring performs more work than necessary. Anagram verification only depends on character frequencies, not character order.

A fixed array of size 26 can represent the frequency of every lowercase English letter. One frequency array stores the target counts. A new frequency array is built for every candidate substring. Equal arrays confirm an anagram without sorting.

The approach removes repeated sorting, but every new window still recounts all M characters from the beginning.

Algorithm

  • Store the lengths of s and p as N and M.

  • Return an empty result when M > N.

  • Initialize a frequency array targetCount of size 26.

  • Traverse p and increase the frequency associated with every character.

  • Traverse every valid starting index from 0 to N - M.

  • Initialize a new frequency array windowCount of size 26 for the current substring.

  • Traverse all M characters beginning at the current starting index and update windowCount.

  • Compare windowCount with targetCount.

  • Append the starting index when both arrays match.

  • Return the result after processing every candidate substring.

Dry Run

fa

fa

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Finds all anagram starts by recounting
every candidate window. */
vector<int> findAnagrams(string s, string p) {
vector<int> result;
int n = s.length();
int m = p.length();
// Stop when no window can match the target length.
if (m > n) {
return result;
}
// Store target frequencies for lowercase letters.
vector<int> targetCount(26, 0);
for (char character : p) {
targetCount[character - 'a']++;
}
// Build a fresh frequency array for every window.
for (int start = 0; start + m <= n; start++) {
vector<int> windowCount(26, 0);
// Count all characters in the current window.
for (int offset = 0; offset < m; offset++) {
char character =
s[start + offset];
windowCount[character - 'a']++;
}
// Equal frequencies confirm an anagram.
if (windowCount == targetCount) {
result.push_back(start);
}
}
return result;
}
};
// Driver code to execute the solution.
int main() {
string s = "cbaebabacd";
string p = "abc";
Solution solution;
vector<int> answer =
solution.findAnagrams(s, p);
// Print the resulting indices.
cout << "[";
for (
int index = 0;
index < (int)answer.size();
index++
) {
cout << answer[index];
if (index + 1 < (int)answer.size()) {
cout << ", ";
}
}
cout << "]" << endl;
return 0;
}

Complexity Analysis

Time Complexity: O((N - M + 1) × M), simplified to O(N × M), where N represents the length of s and M represents the length of p. Every candidate window recounts all M characters. Comparing two arrays of size 26 requires constant alphabet work.

Space Complexity: O(26), simplified to O(1) auxiliary space, excluding the returned indices. A result containing A matching indices requires O(A) output space.

Optimal Approach

The Better Approach avoids sorting but rebuilds the complete frequency array for every window. Two consecutive windows share M - 1 characters, so recounting the shared portion repeats unnecessary work.

A fixed-size Sliding Window preserves the current frequency array. Moving the window one position to the right causes only two changes:

  • One character leaves from the left.

  • One character enters from the right.

Updating those two frequencies keeps the complete window state available in constant time. Frequency equality after every movement identifies all anagram starting positions, including overlapping occurrences.

Algorithm

  • Store the lengths of s and p as N and M.

  • Return an empty result when M > N.

  • Initialize two arrays of size 26:

    • targetCount for character frequencies in p.

    • windowCount for character frequencies in the active window of s.

  • Traverse the first M positions.

    • Increase the frequency of p[index] inside targetCount.

    • Increase the frequency of s[index] inside windowCount.

  • Append index 0 when both frequency arrays match.

  • Traverse right from M to N - 1.

  • Add the incoming character s[right] to windowCount.

  • Remove the outgoing character s[right - M] from windowCount, maintaining a window of exactly M characters.

  • Calculate the new starting index as right - M + 1.

  • Append the new starting index when windowCount matches targetCount.

  • Return the result after the right boundary reaches the end of s.

Dry Run

fa

fa

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Finds all anagram starts
with a sliding window. */
vector<int> findAnagrams(string s, string p) {
vector<int> result;
int n = s.length();
int m = p.length();
// Stop when no window can match the target length.
if (m > n) {
return result;
}
vector<int> targetCount(26, 0);
vector<int> windowCount(26, 0);
// Build target counts and the first window.
for (int index = 0; index < m; index++) {
targetCount[p[index] - 'a']++;
windowCount[s[index] - 'a']++;
}
// Record the first window when frequencies match.
if (windowCount == targetCount) {
result.push_back(0);
}
// Move the fixed-size window across the string.
for (int right = m; right < n; right++) {
char incoming = s[right];
char outgoing = s[right - m];
// Add the incoming right-side character.
windowCount[incoming - 'a']++;
// Remove the outgoing left-side character.
windowCount[outgoing - 'a']--;
// Record the new window when frequencies match.
if (windowCount == targetCount) {
int start =
right - m + 1;
result.push_back(start);
}
}
return result;
}
};
// Driver code to execute the solution.
int main() {
string s = "cbaebabacd";
string p = "abc";
Solution solution;
vector<int> answer =
solution.findAnagrams(s, p);
// Print the resulting indices.
cout << "[";
for (
int index = 0;
index < (int)answer.size();
index++
) {
cout << answer[index];
if (index + 1 < (int)answer.size()) {
cout << ", ";
}
}
cout << "]" << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N) because target and initial-window construction requires O(M) time, followed by N - M window movements. Every movement changes two frequencies and compares two fixed arrays of size 26, which remains constant alphabet work.

Space Complexity: O(26), simplified to O(1) auxiliary space, excluding the returned indices. A result containing A matching starting indices requires O(A) output space.

FAQs about Find All Anagrams in a String

1. Why must every candidate substring have the same length as p?

An anagram uses every target character exactly once. A shorter or longer substring cannot contain the same complete frequency distribution.

2. Why do equal frequency arrays confirm an anagram?

Every frequency-array position represents one lowercase English letter. Equal values at all 26 positions mean that both strings contain identical character counts.

3. Why is the outgoing character located at right - M?

After adding s[right], the active range temporarily contains M + 1 characters. Index right - M represents the oldest character and must leave to restore the required window size.

4. Can overlapping anagrams be detected?

Yes. Moving the window by one position checks every possible starting index, so overlapping matches remain included.

For s = "abab" and p = "ab", valid windows begin at indices 0, 1, and 2.

5. Why is an array of size 26 sufficient?

Both strings contain lowercase English letters only. Character 'a' maps to index 0, while character 'z' maps to index 25.

6. What happens when p is longer than s?

No length-M substring can exist inside s. An empty list is returned immediately.

7. Are the returned indices always in increasing order?

The provided implementations traverse s from left to right, so indices naturally appear in increasing order. The problem also accepts any order.

8. Can a Hash Map replace the frequency array?

Yes. A Hash Map supports larger or unknown character sets. A fixed array remains simpler and faster for a known lowercase-English alphabet.

9. Can repeated comparison of all 26 entries be removed?

Yes. A mismatch counter can track the number of unequal frequency positions. Every incoming or outgoing character changes only one position, allowing constant-time validity checks without scanning all 26 entries.

Sliding WindowHashingString

Read Similar Blogs

HashingData Structures

Count Distinct Elements

Given an integer array arr[] , return the count of all distinct elements in the array. Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 , and 30 . 10 an...

76.5k
RecursionArraysTrieStringData Structures

Number of Distinct Substrings in a String

cpp #include using namespace std; class Solution { public: /* Counts distinct substrings by generating all substrings and storing the unique ones in a hash set. */ int countDistinctSubstrings(strin...

111.1k
Hashing

Common elements in two arrays

Given two arrays, find all elements that appear in both arrays. Return the common elements without duplicates, in any order. If no common element exists, return an empty array. Input: a = [1, 2, 3,...

84.2k
Comments0