Show problems as
Classic problem #3302MediumTwo PointersStringDynamic ProgrammingGreedy

Find the Lexicographically Smallest Valid Sequence

Real-world version: Cheapest Probe Slots On A Reel
Tracked in this browser only
Read Find the Lexicographically Smallest Valid Sequence on LeetCode(opens in a new tab)

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

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

Python
def cheapest_probe_slots(reel: str, pattern: str) -> list[int]:
Java
public int[] cheapestProbeSlots(String reel, String pattern)

More on the same topics