Free Strings lessonsStrings · Stage 3 · Windows on text · Step 2

Slide the letter counts

Find every place where a rearrangement of a word appears. About 10 minutes.

Hunting for scrambled copies

A word game asks: where in this long text does a scrambled version of "abc" appear? A stretch of text is a scrambled copy when it's the same length and has the same letter counts.

So slide a window exactly as long as the word along the text, and compare its letter counts with the word's counts at every stop.

Same length, same counts: that's a scrambled copy.

s = "cbaebabacd", p = "abc" (windows of 3)

leftright

starts: [0]
window: a1 b1 c1

First window "cba": counts a1 b1 c1, same as p. Start 0 is an answer.

Move 1 of 5

Update the counts, don't recount

Counting all the letters in the window from scratch at every stop repeats work. When the window slides one step, only two counts change: one up for the letter coming in, one down for the letter going out. The other 24 stay the same.

That keeps each slide to a couple of quick updates, however long the word is.

Two updates per slide: one letter in, one letter out.

In code

need = [0] * 26
have = [0] * 26
for ch in p:
    need[ord(ch) - 97] += 1
starts = []
for i, ch in enumerate(s):
    have[ord(ch) - 97] += 1
    if i >= len(p):
        have[ord(s[i - len(p)]) - 97] -= 1
    if have == need:
        starts.append(i - len(p) + 1)
return starts

Quick check

The word is "ab" and the text is "abab". Which windows are scrambled copies of the word?

AStarting at 0, 1 and 2
BStarting at 0 and 2
COnly starting at 0

Show the answer

Starting at 0, 1 and 2. "ab", "ba" and "ab" each have one a and one b.

Your problem

Find the anagrams

You get a text s and a word p, both lowercase. Return the start positions of every window of s that is a rearrangement of p, from smallest to largest.

Example

s = "cbaebabacd", p = "abc" → [0, 6]

0 ≤ lengths ≤ 100,000 · only a to z

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.