Oracle OA 2023 - 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' arbitrarily. 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.

Example:

Consider:

• binary = "110100"
• arr = ["?110?1", "111?2"]

For arr[0] = "?110?1", it 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.

Function Description:

Complete the function checkStrings in the editor below. checkStrings has the following parameters:

• string binary: the string to alter.
• string arr[n]: the strings to match.

Returns:

• string[n]: each i-th string is "YES" or "NO" and relates to the i-th element of arr.

Constraints:

• (1 <= |binary| <= 3000)
• (1 <= n <= 3000)
• ( |arr[i]| = |binary| )
• String binary contains characters '0' and '1' only.
• Each string arr[i] contains characters '0', '1', and '?' only.

Sample Input for Custom Testing

STDIN

101011
2
???111
001101


FUNCTION

binary = "101011"
arr[] size n = 2
arr = ["???111", "001101"]

Sample Output

YES
NO

Explanation

• arr[0] can be converted to "100111" then binary can be made to match using these operations:
  • Choose the subsequence of indices {2, 3} and sort, binary becomes "100111". This equals the chosen arr[0].
  • Note that if the string arr[0] is converted to "001111", then also the string binary can be made to match.
• It is not possible to convert string binary to arr[1] using any sequence of operations.