Where does a rearranged pattern appear in a text?

Sliding window Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
from collections import Counter
text, pat = "cbaebabacd", "abc"
m = len(pat)
starts = [i for i in range(len(text) - m + 1)
          if Counter(text[i:i + m]) == Counter(pat)]
print(starts)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [0, 6]

Right: 'cba' at 0 and 'bac' at 6.

This brute version re-counts every window; the page's solution gets the same starts by updating counts as the window slides.

Why not the others?
  • B [0]. 'bac' at index 6 has the same letters too.
  • C [0, 5, 6]. 'aba' at index 5 has two a's and no c.

30-second answer

Keep letter counts for a window the size of the pattern. Slide it one character at a time, adding the entering letter and removing the leaving one, and record the start whenever the window's counts equal the pattern's. With a fixed alphabet each comparison is O(1), so the scan is O(n), and the two counters take O(1) space.

Practise saying it · 45 s. No recording, just a timer

Explain the fixed window with letter counts.

Say your answer out loud, then check which of these points you covered:

  • Counts for pattern and window
  • Add entering, remove leaving
  • O(n) for a fixed alphabet

Deep dive

Comparing two Counters is O(distinct letters); with lowercase letters that is at most 26, so effectively constant.

A sharper version tracks how many letters currently match their target count, making each slide strictly O(1).

Sorting every window would cost O(n·m log m).

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
from collections import Counter


def pattern_starts(text: str, pattern: str) -> list[int]:
    m = len(pattern)
    if m == 0 or m > len(text):
        return []
    need = Counter(pattern)
    have = Counter(text[:m])
    starts = [0] if have == need else []
    for i in range(m, len(text)):
        have[text[i]] += 1
        have[text[i - m]] -= 1
        if have == need:
            starts.append(i - m + 1)
    return starts

Common mistakes

  • Leaving zero-count keys in the Counter and then comparing with ==. In Python 3.10+ Counter equality treats missing and zero counts as equal, but older code paths and plain dicts do not.
  • Forgetting the window at the very end of the text.

Senior take & follow-ups

Mention the 'matched letters' counter as the optimisation after the Counter version works.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if the pattern is longer than the text?

    Show hint

    Return an empty list straight away.

  2. How would you find the shortest window containing all pattern letters?

    Show hint

    Use a variable window that shrinks while every count is still covered.

What each operation costs: Arrays · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.