Cheapest Wildcard Fill
MediumPrefix Sum ยท Amazon
Given a string s of '0', '1' and '?', replace every '?' with '0' or '1'.
Every pair of positions i < j (any distance apart) with s[i] = '0' and s[j] = '1' costs x. Every pair with s[i] = '1' and s[j] = '0' costs y. Return the minimum possible total cost over all replacements.
Example 1
- Input:
- s = "1?0?", x = 2, y = 5
- Output:
- 12
- Explanation
- Filling it as
"1101"has two10pairs (cost 10) and one01pair (cost 2).
Example 2
- Input:
- s = "?1?0", x = 3, y = 1
- Output:
- 3
Example 3
- Input:
- s = "0?1?0", x = 5, y = 5
- Output:
- 20
Constraints
1 <= s.length <= 2 * 10^4scontains only'0','1'and'?'0 <= x, y <= 10^4