Find All Anagram Start Indices
Medium About 20 min Free, no account needed
Every position where an anagram of the pattern begins.
The brief
Given lowercase strings pattern and text, return every start index (in
ascending order) where an anagram of pattern begins in text.
The obvious approach counts the letters of every window from scratch, O(n * m). The hidden test hides one 10,000-character anagram inside 50,000 characters, so recounting each window is too slow. You need to update each window from the previous one instead of recounting it, O(n + m).
Starter code
using System;
public class Solution
{
// TODO: return all start indices (ascending) of anagrams of pattern inside text.
public int[] FindAnagrams(string pattern, string text)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Sliding window
- Grow and shrink a contiguous range while maintaining its state incrementally.
- Hash maps and sets
- Trade memory for constant-time lookups, membership tests and frequency counts.
Related katas
- Minimum Window Substring (Length) Hard Free Length of the shortest window of text covering every required character.
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.
- Degree of an Array Medium Free Find the shortest contiguous slice whose most-frequent-element count matches the whole array.
- Count Quadruples Summing to Target Medium Free Count index quadruples that sum to a target - without the quadruple loop.