Show problems as
Classic problem #438MediumHash TableStringSliding Window

Find All Anagrams in a String

Real-world version: Mosaic Bundle Positions
Tracked in this browser only
Read Find All Anagrams in a String on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstSliding Window · Strings, animated step by step

A tiler is repairing a mosaic border. The finished border is written down as border, one lowercase letter per tile in the order the tiles run left to right, each letter standing for a colour. A sealed box of spare tiles is written down the same way as bundle.

The tiler wants to know where a single box could have supplied a run of the border. A box supplies the run starting at position i when that run is exactly as long as the box and holds the same colours in the same quantities, in whatever order they happen to be laid. Quantities matter: a box holding two red tiles cannot supply a run holding one red tile and two blue ones.

Return the starting positions of every run the box could supply, listed from smallest position to largest. Return an empty list when there is no such run, which includes the case of a box holding more tiles than the whole border.

Examples

Example 1

Input
border = "tsrrtsr", bundle = "rst"
Output
[0, 3, 4]

The runs beginning at 0, 3 and 4 each hold one t, one s and one r. The run beginning at 4 reaches the end of the border, so the last run counts as well.

Example 2

Input
border = "rssrrs", bundle = "rrs"
Output
[2, 3]

The box holds two r tiles and one s. The run beginning at 0 draws on the same two colours but in the wrong quantities, so only the runs at 2 and 3 qualify.

Example 3

Input
border = "mm", bundle = "mmm"
Output
[]

The box holds three tiles and the border only has two, so no run can be as long as the box.

Constraints

  • 1 <= border.length <= 3 * 10^4
  • 1 <= bundle.length <= 3 * 10^4
  • border and bundle consist of lowercase English letters
  • bundle may hold more tiles than border, in which case the answer is empty

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def bundle_positions(border: str, bundle: str) -> list[int]:
Java
public List<Integer> bundlePositions(String border, String bundle)

More on the same topics