0219HardHash TableStringSliding Window

Code Tape Offsets

Tracked in this browser only

Trains the technique from

LeetCode 30Substring with Concatenation of All Words

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def code_tape_offsets(tape: str, codes: list[str]) -> list[int]:

Java

public List<Integer> codeTapeOffsets(String tape, String[] codes)

The intended approach

Time O(n * w) where n is the tape length and w the code lengthSpace O(n + c * w) for the flag array and the two tallies, where c is the number of distinct codes

Because every entry has the same length `w`, a block start fixes which letters form each code, and two block starts that differ by a multiple of `w` chop the tape the same way. So run `w` separate passes, one per remainder of the position divided by `w`, and in each pass read the tape one code-sized chunk at a time while holding a window of chunks together with a tally of how many of each code it holds. A chunk that is not on the run sheet empties the window; a chunk that pushes its own tally above what the sheet asks for drops chunks off the front of the window until it no longer does; and a window holding exactly `len(codes)` chunks records its start and then gives up its first chunk. Marking the starts in a flag array keeps the answer in increasing order without an ordering step.

Pythonentry point: code_tape_offsets

def code_tape_offsets(tape, codes):
    width = len(codes[0])
    count = len(codes)
    span = width * count
    n = len(tape)
    if span > n:
        return []
    need = {}
    for code in codes:
        need[code] = need.get(code, 0) + 1
    hit = [False] * n
    for phase in range(width):
        have = {}
        filled = 0
        left = phase
        pos = phase
        while pos + width <= n:
            chunk = tape[pos:pos + width]
            pos += width
            if chunk in need:
                have[chunk] = have.get(chunk, 0) + 1
                filled += 1
                while have[chunk] > need[chunk]:
                    dropped = tape[left:left + width]
                    have[dropped] -= 1
                    filled -= 1
                    left += width
                if filled == count:
                    hit[left] = True
                    dropped = tape[left:left + width]
                    have[dropped] -= 1
                    filled -= 1
                    left += width
            else:
                have = {}
                filled = 0
                left = pos
    return [i for i in range(n) if hit[i]]

The obvious version

Try every position outright: chop the block-sized stretch that starts there into code-sized pieces, tally them and compare the tally with the run sheet. O(n * len(codes) * w).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_code_tape_offsets(tape, codes):
    width = len(codes[0])
    span = width * len(codes)
    want = {}
    for code in codes:
        want[code] = want.get(code, 0) + 1
    out = []
    for start in range(len(tape) - span + 1):
        got = {}
        for at in range(start, start + span, width):
            piece = tape[at:at + width]
            got[piece] = got.get(piece, 0) + 1
        if got == want:
            out.append(start)
    return out

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in