0867MediumArrayTwo PointersStringGreedy

Matching a Pattern by Sorting a Subsequence

Tracked in this browser only

Trains the technique from

LeetCode 3998Transform Binary String Using Subsequence Sort

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 reads s, a string of '0' and '1'. Each entry of strs is a pattern of the same length made of '0', '1' and '?', where '?' accepts either character.

One tidy picks any subsequence of positions of the tape and rewrites the characters at exactly those positions in non-decreasing order, leaving the rest of the tape untouched. Picking no positions is allowed.

For each pattern, decide whether one tidy can turn the tape into a string the pattern accepts. Return the positions in strs of the patterns for which it can, in increasing order.

Examples

Example 1

Input: s = "1010", strs = ["0011", "1010", "0101", "??0?"]
Output: [0, 1, 3]

Picking every position and sorting gives "0011", which the first pattern accepts. The second pattern already matches the tape, so picking nothing works. The fourth needs only a zero at position 2, which the tape already has.

Example 2

Input: s = "111", strs = ["000", "111", "??1"]
Output: [1, 2]

The tape holds no zero, so no tidy can produce one, and the first pattern is out of reach. The other two are already satisfied.

Example 3

Input: s = "0", strs = ["0", "1", "?"]
Output: [0, 2]

A tape of one character cannot be changed by sorting, so only the patterns that already accept it are reachable.

Constraints

1 <= s.length <= 2000
1 <= strs.length <= 2000
s[i] is either '0' or '1'
Every pattern in strs has the same length as s
strs[i][j] is '0', '1' or '?'

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 patterns_reachable(s: str, strs: list[str]) -> list[int]:

Java

public List<Integer> patternsReachable(String s, List<String> strs)

The intended approach

Time O(P * n) for P patterns over a tape of length n.Space O(1) beyond the answer: each pattern is settled with a few running counts.

A tidy rewrites the picked positions as every zero it picked up followed by every one, and it never invents a character, so whatever it does the picked positions keep the same number of zeros. That forces two things at once. First, a position turned from a one into a zero must be paid for by some other picked position turned from a zero into a one, so those two kinds of change come in equal numbers. Second, since the zeros land first, every position turned into a zero has to sit to the left of every position turned into a one. Nothing else is needed: once those two conditions hold, picking exactly the changing positions already works, so extra positions never help. So per pattern, walk the tape and split the forced changes into the two kinds. Reject at once if the last forced turn-to-zero sits right of the first forced turn-to-one. If the two counts already agree, the pattern is reachable. Otherwise the shortfall has to come from wildcards, and which wildcards qualify depends on the side that is short: a wildcard can supply a turn-to-zero only where the tape holds a one and it lies left of every forced turn-to-one, and it can supply a turn-to-one only where the tape holds a zero and it lies right of every forced turn-to-zero. Count the qualifying wildcards on the short side and compare against the shortfall.

Pythonentry point: patterns_reachable

def patterns_reachable(s, strs):
    n = len(s)
    out = []
    for at, pat in enumerate(strs):
        to_zero = 0          # forced turns from a one into a zero
        to_one = 0           # forced turns from a zero into a one
        last_zero = -1       # rightmost forced turn-to-zero
        first_one = n        # leftmost forced turn-to-one
        for i in range(n):
            want = pat[i]
            if want == "?" or want == s[i]:
                continue
            if want == "0":
                to_zero += 1
                last_zero = i
            else:
                to_one += 1
                if i < first_one:
                    first_one = i
        # the sorted run lays its zeros first, so no forced zero may sit right of a forced one
        if last_zero > first_one:
            continue
        if to_zero == to_one:
            out.append(at)
            continue
        if to_zero < to_one:
            # short of turns-to-zero: only a wildcard over a one, left of every forced one, helps
            spare = 0
            for i in range(first_one):
                if pat[i] == "?" and s[i] == "1":
                    spare += 1
            if spare >= to_one - to_zero:
                out.append(at)
        else:
            # short of turns-to-one: only a wildcard over a zero, right of every forced zero, helps
            spare = 0
            for i in range(last_zero + 1, n):
                if pat[i] == "?" and s[i] == "0":
                    spare += 1
            if spare >= to_zero - to_one:
                out.append(at)
    return out

The obvious version

For each pattern, try every subsequence of positions, sort the characters at exactly those positions, and check whether the result is accepted. Exponential in the tape length, but it applies the rule literally and assumes nothing about which positions are worth picking.

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_patterns_reachable(s, strs):
    n = len(s)
    out = []
    for at, pat in enumerate(strs):
        found = False
        for mask in range(1 << n):
            spots = [i for i in range(n) if mask >> i & 1]
            picked = sorted(s[i] for i in spots)
            built = list(s)
            for k, i in enumerate(spots):
                built[i] = picked[k]
            good = True
            for i in range(n):
                if pat[i] != "?" and pat[i] != built[i]:
                    good = False
                    break
            if good:
                found = True
                break
        if found:
            out.append(at)
    return out

How this problem was checked

Reference solution executed against 14 test cases — 14 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