Find All Anagrams — Problem Statement & Solution Guide
Problem Description
Given a string s and a pattern p, find all starting positions in s where p (or its rearrangement) occurs.
Examples
Input
s = 'gcagtacg', p = 'gca'
Output
[0, 3]
Explanation: Step 1: Create a hashmap to store the frequency of characters in the pattern. The hashmap will be {'g': 1, 'c': 1, 'a': 1}. Step 2: Create a sliding window of size equal to the length of the pattern. Iterate over the string and for each window, calculate the frequency of characters in the window. Step 3: If the frequency of characters in the window is equal to the frequency of characters in the pattern, add the starting position of the window to the result list. Step 4: Return the result list.
Input
s = 'abab', p = 'ab'
Output
[0, 1]
Explanation: Step 1: Create a hashmap to store the frequency of characters in the pattern. The hashmap will be {'a': 1, 'b': 1}. Step 2: Create a sliding window of size equal to the length of the pattern. Iterate over the string and for each window, calculate the frequency of characters in the window. Step 3: If the frequency of characters in the window is equal to the frequency of characters in the pattern, add the starting position of the window to the result list. Step 4: Return the result list.
Constraints
- 1 <= s.length, p.length <= 3 * 10^4
Optimal Approach & Strategy
Sliding window with character frequency arrays. If arrays match, increment count. Slide by decrementing outgoing char and incrementing incoming char. Time O(N), Space O(1).
Brute Force Approach
Compare every p.length substring of s with p. Time O(N*M).
Verified Code Solutions
class Solution {
public int[] findAnagrams(String s, String p) {
if (s.length() < p.length()) {
return new int[0];
}
int[] p_count = new int[256];
int[] s_count = new int[256];
for (int i = 0; i < p.length(); i++) {
p_count[p.charAt(i)]++;
s_count[s.charAt(i)]++;
}
int[] anagram_positions = new int[s.length() - p.length() + 1];
int index = 0;
for (int i = p.length(); i < s.length(); i++) {
s_count[s.charAt(i)]++;
s_count[s.charAt(i - p.length())]--;
if (isAnagram(p_count, s_count)) {
anagram_positions[index++] = i - p.length() + 1;
}
}
return Arrays.copyOf(anagram_positions, index);
}
private boolean isAnagram(int[] p_count, int[] s_count) {
for (int i = 0; i < 256; i++) {
if (p_count[i] != s_count[i]) {
return false;
}
}
return true;
}
}def findAnagrams(s, p):
if len(s) < len(p):
return []
p_count = {}
s_count = {}
for i in range(len(p)):
p_count[p[i]] = p_count.get(p[i], 0) + 1
s_count[s[i]] = s_count.get(s[i], 0) + 1
anagram_positions = []
for i in range(len(p), len(s)):
s_count[s[i]] = s_count.get(s[i], 0) + 1
s_count[s[i - len(p)]] -= 1
if s_count == p_count:
anagram_positions.append(i - len(p) + 1)
return anagram_positionsAsked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.