Show problems as
Classic problem #30HardHash TableStringSliding Window

Substring with Concatenation of All Words

Real-world version: Code Tape Offsets
Tracked in this browser only
Read Substring with Concatenation of All Words on LeetCode(opens in a new tab)

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

A sorting line prints one unbroken strip of lowercase letters, handed to you as tape. A run sheet lists the codes the line was told to stamp, handed to you as codes. Every entry of codes has the same length, and an entry may be listed more than once.

A block is a stretch of the tape that is exactly the entries of codes written one after another in some order, with nothing in between and nothing left over. The order is free, but the tally is not: an entry listed twice must be written twice inside the block, so every block is len(codes) codes long.

Return the position of every block start, counted from 0 and given in increasing order. Report each position once. Return an empty list when the tape holds no block. Block positions may overlap.

Examples

Example 1

Input
tape = "zzabcbcayy", codes = ["abc", "bca"]
Output
[2]

From position 2 the tape reads abcbca, which is abc then bca, so both run-sheet entries appear once each. No other position starts six letters that split into those two codes.

Example 2

Input
tape = "abababab", codes = ["ab", "ab"]
Output
[0, 2, 4]

The run sheet asks for ab twice, so a block is four letters long. Positions 0, 2 and 4 each read abab, which splits into ab and ab. Position 1 reads baba and position 3 reads baba, neither of which splits into two copies of ab.

Example 3

Input
tape = "ababcd", codes = ["ab", "cd"]
Output
[2]

Position 2 reads abcd, which is ab then cd. Position 0 reads abab, which repeats ab and never stamps cd, so the tally does not match.

Constraints

  • 1 <= tape.length <= 10^4
  • 1 <= codes.length <= 5000
  • 1 <= codes[i].length <= 30
  • every entry of codes has the same length
  • tape and codes[i] hold lowercase English letters only

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 code_tape_offsets(tape: str, codes: list[str]) -> list[int]:
Java
public List<Integer> codeTapeOffsets(String tape, String[] codes)

More on the same topics