Binary string satisfying several constraints

Question

I'm trying to solve this problem, but without success.

Problem: You're given a binary string where some of the bits are replaced by ?. You're also given several intervals [$l_i$, $r_i$] ($l_i < r_i$). Find a binary string S with ? replaced by 0 or 1, such that in each interval [$l$, $r$], s[$l..r$] includes both 0 and 1.

Example:

Given the string 00?11 and the interval [2, 3], the string 00111 satisfies the requirements, as S[2..3]=01 include both 0 and 1.

However, the string 00?11 and the intervals [2, 3] and [3, 4] cannot be solved, as the ? would have to be both 0 and 1.

The bounds are |S|,Q<=1e5

I tried using greedy, but it's giving wrong answer for this case: 0??0, [1, 3], [2, 3] and [3, 4], as the greedy algorithm would try 0??0 -> 01?0 -> 0100 -> fail, yet there exists a solution (0010).

I tried removing completely overlapping intervals (such as [1, 3] and [2, 3]), but there're other cases I found that fails. What would be a correct solution?

Thanks.

Answer 1

There are 4 types of intervals:

1. Intervals containing both $0$ and $1$ (e.g. 00?11?). Such intervals are already satisfied, and we simply ignore them.

2. Intervals which can't be satisfied: either of length 1 (e.g. 0, ?), or contain only 0's or 1's (e.g. 000, 111). If such an interval exists, report "no solutions".

3. Intervals which consist only of 0's or only of 1's and have a single ? (e.g. 00?0, 1?). For such intervals, we know what ? must be - so we just set ?, satisfying the interval, and ignore the interval from now on.

4. Intervals which have more than one ?. We'll talk about them later.

The first phase of the algorithm is to get rid of Types 1, 2, 3. Note that when we satisfy an interval of Type 3, other intervals can change their Type.

while (true) {
    Remove all intervals of Type 1
    Check that there are no intervals of Type 2
    if (there exists an interval of Type 3) {
        Satisfy and remove this interval
    } else {
        break
    }
}

As a result, only intervals of Type 4 remain. Each such interval has two ?. In particular, it covers two consecutive remaining ?'s. Therefore, it suffices to assign to the remaining ?'s values 0, 1, 0, 1, 0, 1, ..., from left to right.

---

Now, the efficient algorithm for the first phase. We process all intervals in increasing order of their right ends. We maintain a set of intervals $T_4$ (initially empty) of currently encountered Type 4 intervals, sorted by their left ends.

For each new interval, depending on their type, we do the following:

• Type 1: Ignore it

• Type 2: Return "no solutions"

• Type 4: Add an interval into $T_4$.

• Type 3: Satisfy it. Now we look into the rightmost interval $I$ in $T_4$ (i.e. with the largest left end). If it changed its type, remove it from $T_4$ and process it again (i.e. check its type and apply the corresponding action from this list). Otherwise do nothing: since $I$ didn't change its type, other intervals in $T_4$ also won't change their type.

  Indeed, let $I'$ be another interval from $T_4$. If $I \subseteq I'$, we are fine (if $I$ has two ?, then $I'$, which contains $I$, also has them). Let $i$ be the position of the fixed ?. If $i > right(I')$, then we are fine. Otherwise, we have $i \le right(I') < right(I)$. But note that there are no ? between $right(I')$ and $right(I)$: otherwise, the currently processed interval wouldn't be Type 3, since it has at least two ?'s. Therefore, $I \cap I'$ has at least two ?'s, and therefore, $I'$ too.

While processing Type 3, we find the rightmost interval $I$ in $T_4$ until $T_4$ is empty or $I$ didn't change its type. Simply put, we remove intervals from $S$ while there are intervals which change their type.