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\).