0325MediumTwo PointersStringDynamic ProgrammingGreedy

Cheapest Probe Slots On A Reel

Tracked in this browser only

Trains the technique from

LeetCode 3302Find the Lexicographically Smallest Valid Sequence

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 tape reel carries a long strip of lowercase letters, word1. A test rig needs to punch a probe hole at some of the slots so that reading the punched slots front to back reproduces a short target strip, word2.

Pick strictly increasing slot numbers p[0] < p[1] < ... < p[m-1], where m is the length of word2. The rig tolerates at most one disagreement: the number of positions t with word1[p[t]] != word2[t] may be 0 or 1, never more.

Among all tolerable choices, return the one whose slot list is lexicographically smallest: compare two lists entry by entry from the front, and the list with the smaller entry at the first differing spot wins. If no tolerable choice exists, return an empty array.

Examples

Example 1

Input: word1 = "caa", word2 = "ab"
Output: [1, 2]

Slots 1 and 2 are increasing and read `aa` against the target `ab`, which is one disagreement, so the choice is tolerable.

Example 2

Input: word1 = "abcde", word2 = "cd"
Output: [0, 3]

Slots 0 and 3 read `ad` against the target `cd`, disagreeing only at the first position.

Example 3

Input: word1 = "aaa", word2 = "bb"
Output: []

Every pair of slots reads `aa`, which disagrees with `bb` in both positions, so the empty array is returned.

Example 4

Input: word1 = "ccabc", word2 = "abc"
Output: [0, 3, 4]

Slots 0, 3 and 4 are increasing and read `cbc` against `abc`, a single disagreement at the first position.

Constraints

1 <= word2.length < word1.length <= 3 * 10^5
word1 and word2 consist only of lowercase English letters.

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 cheapest_probe_slots(reel: str, pattern: str) -> list[int]:

Java

public int[] cheapestProbeSlots(String reel, String pattern)

The intended approach

Time O(n + m)Space O(n) for the suffix table plus O(m) for the returned list

First sweep the reel right to left recording, for every start, the longest suffix of the target that still fits there as a plain subsequence. Then sweep left to right: an exact letter hit is always taken because it uses the smallest free slot and costs nothing, and when the letters differ the substitution is spent on that slot only if the recorded suffix table says the rest of the target still fits exactly after it.

Pythonentry point: cheapest_probe_slots

def cheapest_probe_slots(reel, pattern):
    # tail[i] = how long a suffix of pattern still fits as a subsequence of
    # reel[i:]. Built right to left, then one greedy left-to-right sweep: take
    # every exact hit, and spend the single allowed substitution on the earliest
    # slot whose remainder is still coverable exactly.
    # Time O(n + m). Space O(n) for tail plus O(m) for the answer.
    n = len(reel)
    m = len(pattern)
    tail = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        k = tail[i + 1]
        if k < m and reel[i] == pattern[m - 1 - k]:
            tail[i] = k + 1
        else:
            tail[i] = k
    picked = []
    j = 0
    spent = False
    for i in range(n):
        if j == m:
            break
        if reel[i] == pattern[j]:
            picked.append(i)
            j += 1
        elif not spent and tail[i + 1] >= m - (j + 1):
            spent = True
            picked.append(i)
            j += 1
    return picked if j == m else []

The obvious version

Walk every increasing slot combination in lexicographic order, count disagreements, and return the first combination with at most one.

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_cheapest_probe_slots(reel, pattern):
    from itertools import combinations
    n = len(reel)
    m = len(pattern)
    for idx in combinations(range(n), m):
        off = 0
        for a, b in zip(idx, pattern):
            if reel[a] != b:
                off += 1
                if off > 1:
                    break
        if off <= 1:
            return list(idx)
    return []

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
4 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