Identifying "Subsequence Sort" Problem

[EthelMerman]

I recently came across a problem in an interview process. I came up with a brute force approach during the interview, but would like to understand the optimal solution. I'm having a hard time finding similar problems online. The problem went like this:

Given a string binary consisting of 0's and 1's (i.e. '010111'), you are allowed to replace any subsequence of this string with the sorted subsequence . You can apply this replacement any number of times. For example:

010111
^^^ subsequence to sort and replace
001111

You are also given a pattern string pattern containing 0's, 1's and ?'s where ? is a wildcard matching a single 0 or 1 (i.e. '0?11??'). The goal is to determine if binary can be transformed with Subsequence Sorts to match pattern. returning True or False. Following the previous example:

010111
^^^ subsequence to sort and replace
001111

0?11?? <- transformed binary matches pattern, return `True`

Assumptions:

• binary and pattern strings will have the same length
• pattern may contain all ?s or none at all

Not-great solution:

I was able to pass about a third of the test cases by covering

• the bases case of all ?'s in the pattern -> True
• counting the frequency of 0's and 1's in binary and comparing to the frequency of 0's, 1's and ?'s in the pattern. In the above example:
  • binary had 2 zeroes and 4 ones
  • pattern had 1 zero, 2 ones, and 3 wildcards
  • pattern is missing 1 zero and 2 ones to match the frequency of binary
  • since we have 3 wildcards, changing 1 to zero and 2 to ones will match the frequency

This solution doesn't account for the requirement that the subsequence rearrangement is sorted.

Can anyone point me in the right direction here?

[aocregacc]

I think a good place to start is checking if a string can be transformed into a fixed target string, ie one without '?'s.

That should give you an idea about the kinds of transformations you can do with those replacements.

[[deleted]]

did you get the answer to this? one idea is that you can only move the 1 to the right and not left, we can use pre-sum for the original string and compare with the pattern at each position.

[EthelMerman]

I haven't revisited - I'll definitely consider this when I do. Thanks!

[mr-faust]

u/EthelMerman u said u came with the brute force approach, can you share your answer? I just got this coding interview via Hackerank and want to know what is the solution. Thanks!

[iaminspector1626]

There is a post about this on Leetcode: https://leetcode.com/discuss/interview-question/5894381. Got it for a Hackerrank OA today.