Subsequence Sort
Given a binary string binary consisting of characters '0' and '1' only, perform the following 0
or more times.
ยท Choose any subsequence, sort the subsequence, and replace the original subsequence with the sorted sequence.
Next, there is an array of strings, arr, of length n, where each string has length / binary/ and consists of characters '0', '1' and '?'. Each '?' character can be replaced with either '0' or '1' . For each string in arr, after replacing each ?' character with either '0' or '1', determine if it is possible to rearrange binary using the operation described any number of times. If it is possible, store "YES" as the corresponding answer, otherwise store "NO", both without quotes.
Note:
ยท A string a is a subsequence of a string b obtained by deletion of some number (possibly, zero or all) of characters without changing the order of the remaining characters.
ยท Each computation is independent of the others. That is, the string binary is in its original state at the beginning of each array element.
Example
Consider binary = "110100", and arr = ["?110?1","111 ??? "].
- arr[0] = "?110?1"can be converted to "011001"by appropriate replacement of ? characters. This
string can be obtained from binary as follows:
- Choose the subsequence of indices {0,2}, and sort this subsequence, binary becomes "011100".
- Choose the subsequence of indices (3, 4, 5} and sort this subsequence, binary becomes "011001",
which equals arr[0].
: The answer for this element is "YES".
- It is not possible to convert string binary to arr[1] so the answer for this element is "NO".
Return ["YES", "NO"], without quotes.
Asked in:
ShareChat