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.