Editor

Find All Anagram Positions

#113 · Sliding window · Intermediate · 90 XP · about 18 min

Write anagram_positions(text, pattern) that returns, in ascending order, every index i where the slice of text that starts at i and has the same length as pattern is an anagram of pattern: it uses exactly the same letters, the same number of times, in any order. Matches may overlap. If pattern is longer than text, return [].

Examples

anagram_positions('listensilent', 'enlist')   # returns [0, 3, 6]
anagram_positions('abab', 'ab')               # returns [0, 1, 2]
anagram_positions('hello', 'xyz')             # returns []

In the first example the slices 'listen', 'tensil' and 'silent' each use the six letters of 'enlist' once. A slice does not have to be a real word.

Constraints

  • 1 <= len(pattern)
  • 0 <= len(text) <= 100,000
  • Both strings hold only lowercase letters a to z

Ready?

Accept the challenge to start writing. A small timer counts the time this page is in view.

Output appears here.