Cost of 01 and 10 Pairs
Problem
Recently, a friend has met a question in pre-interview machine test:
Given a string \(s\) containing characters 0
, 1
, or ?
, and integer parameters \(x\) and \(y\), while \(1 \leq len(s) < 10^5, 1 \leq x < 10^5, 1 \leq y < 10^5\).
For any string only containing 0
and 1
, we define its cost as
$$x \cdot p_{01} + y \cdot p_{10}$$ while:
- \( p_{01} \): the number of 01 subsequences in \(s\), not substrings, digit 0 and digit 1 needn’t to be neighbors in \(s\).
- \( p_{10} \): the number of 10 subsequences in \(s\).
You should replace all the characters ?
in string \(s\) with characters 0
or 1
to get a string \(s'\), please calculate the minimum cost of all the possible \(s'\).