Show problems as
Classic problem #3998MediumArrayTwo PointersStringGreedy

Transform Binary String Using Subsequence Sort

Real-world version: Matching a Pattern by Sorting a Subsequence
Tracked in this browser only
Read Transform Binary String Using Subsequence Sort on LeetCode(opens in a new tab)

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

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

Python
def patterns_reachable(s: str, strs: list[str]) -> list[int]:
Java
public List<Integer> patternsReachable(String s, List<String> strs)

More on the same topics