Anagram Index Finder — Problem Statement & Solution Guide
Problem Description
Given a string sequence and a string pattern, find all starting positions in sequence where pattern or its anagram occurs. Return a list of such positions.
Examples
Input
sequence = 'abxaba', pattern = 'ab'
Output
[0, 3, 4]
Explanation: Step-by-step: with input sequence 'abxaba' and pattern 'ab', we find all starting positions where pattern or its anagram occurs. We start by sorting the pattern 'ab' to get 'ab'. Then we iterate over the sequence with a sliding window of size 2 (length of pattern). At each position, we sort the substring in the window and compare it with the sorted pattern. If they match, we add the current position to the result list. So, the output is [0, 3, 4].
Input
sequence = 'abcabc', pattern = 'bca'
Output
[1, 4]
Explanation: Step-by-step: with input sequence 'abcabc' and pattern 'bca', we find all starting positions where pattern or its anagram occurs. We start by sorting the pattern 'bca' to get 'abc'. Then we iterate over the sequence with a sliding window of size 3 (length of pattern). At each position, we sort the substring in the window and compare it with the sorted pattern. If they match, we add the current position to the result list. So, the output is [1, 4].
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
function findAnagramPositions(sequence, pattern) {
let result = [];
let patternLength = pattern.length;
let sortedPattern = pattern.split('').sort().join('');
for (let i = 0; i <= sequence.length - patternLength; i++) {
let substring = sequence.substring(i, i + patternLength);
let sortedSubstring = substring.split('').sort().join('');
if (sortedSubstring === sortedPattern) {
result.push(i);
}
}
return result;
}class Solution {
public:
vector<int> findAnagramPositions(string sequence, string pattern) {
vector<int> result;
int patternLength = pattern.length();
sort(pattern.begin(), pattern.end());
for (int i = 0; i <= sequence.length() - patternLength; i++) {
string substring = sequence.substr(i, patternLength);
sort(substring.begin(), substring.end());
if (substring == pattern) {
result.push_back(i);
}
}
return result;
}
};import java.util.Arrays;
public class Solution {
public int[] findAnagramPositions(String sequence, String pattern) {
int[] result = new int[sequence.length()];
int count = 0;
int patternLength = pattern.length();
char[] sortedPattern = pattern.toCharArray();
Arrays.sort(sortedPattern);
for (int i = 0; i <= sequence.length() - patternLength; i++) {
String substring = sequence.substring(i, i + patternLength);
char[] sortedSubstring = substring.toCharArray();
Arrays.sort(sortedSubstring);
if (Arrays.equals(sortedSubstring, sortedPattern)) {
result[count++] = i;
}
}
return Arrays.copyOf(result, count);
}
}def find_anagram_positions(sequence, pattern):
result = []
pattern_length = len(pattern)
sorted_pattern = ''.join(sorted(pattern))
for i in range(len(sequence) - pattern_length + 1):
substring = sequence[i:i + pattern_length]
sorted_substring = ''.join(sorted(substring))
if sorted_substring == sorted_pattern:
result.append(i)
return resultfunction findAnagramPositions(sequence, pattern) {
let result = [];
let patternLength = pattern.length;
let sortedPattern = pattern.split('').sort().join('');
for (let i = 0; i <= sequence.length - patternLength; i++) {
let substring = sequence.substring(i, i + patternLength);
let sortedSubstring = substring.split('').sort().join('');
if (sortedSubstring === sortedPattern) {
result.push(i);
}
}
return result;
}Asked 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.