Oracle OA-6 2023
Problem Description
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:
Assume: 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.binarybecomes"011100". - Choose the subsequence of indices
(3, 4, 5)and sort this subsequence.binarybecomes"011001", which equalsarr[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.
Constraints:
- (1 <= |binary| <= 3000)
- (1 <= n <= 3000)
- ( |arr[i]| = |binary| )
- String
binarycontains characters'0'and'1'only. - Each string
arr[i]contains characters'0','1', and'?'only.
Sample Input
10101111
2
???1001101
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.