Anagram Positions in a Text
Problem
A plagiarism checker looks for scrambled copies of a short key inside a long text. Given lowercase strings text and key, return every start index i where the len(key) letters of text starting at i form an anagram of key, meaning they use exactly the same letters the same number of times. List the indices in ascending order. Both strings have up to 30,000 letters, so re-counting every window from scratch is too slow.
Examples
Input: text = "cbaebabacd", key = "abc"
Output: [0, 6]
Why: "cba" starts at 0 and "bac" starts at 6Input: text = "abab", key = "ab"
Output: [0, 1, 2]
Why: windows may overlap: "ab", "ba", "ab"Input: text = "a", key = "ab"
Output: []
Why: edge case, the key is longer than the textHints
0 / 3
Every candidate is a window of exactly len(key) letters. Sliding it one step changes only two letters: one enters on the right, one leaves on the left.
Keep a count of the letters inside the window and compare it with the key's count. Updating the window count on a slide costs O(1).
Keep a single number, the count of letters whose window count differs from the key's count. Adjust it only for the letter entering and the letter leaving. The window is an anagram exactly when that number is 0.
Solution
The window has a fixed width, so each slide adds one letter on the right and drops one on the left, and only those two letters' counts change. Rather than comparing two full tables each time, the code keeps need[c] as the key's count minus the window's count, plus a tally of how many letters have need[c] ≠ 0. Changing one count can only move that letter in or out of the tally, so the check stays O(1) per slide, and a tally of zero means the window matches the key. Time is O(len(text) + len(key)), and space is O(1) for 26 letters.
from collections import Counter
def anagram_starts(text, key):
k = len(key)
need = Counter(key) # key count minus window count
off = len(need) # letters whose need is not zero
out = []
def change(ch, delta):
nonlocal off
before = need[ch]
need[ch] = before + delta
if before == 0:
off += 1 # was balanced, now is not
elif need[ch] == 0:
off -= 1 # just became balanced
for i, ch in enumerate(text):
change(ch, -1) # letter enters the window
if i >= k:
change(text[i - k], +1) # letter leaves the window
if i >= k - 1 and off == 0:
out.append(i - k + 1)
return out
print(anagram_starts("cbaebabacd", "abc")) # -> [0, 6]
print(anagram_starts("abab", "ab")) # -> [0, 1, 2]
print(anagram_starts("a", "ab")) # -> []Stuck on the idea rather than the code? Sliding Window covers it.