Minimum Cost to Partition a Binary String
You are given a binary string s and two integers encCost and flatCost.
For each index i, s[i] = '1' indicates that the i^th element is sensitive, and s[i] = '0' indicates that it is not.
The string must be partitioned into segments. Initially, the entire string forms a single segment.
For a segment of length L containing X sensitive elements:
- If
X = 0, the cost isflatCost. - If
X > 0, the cost isL * X * encCost.
If a segment has even length, you may split it into two contiguous segments of equal length, and the cost of this split is the sum of costs of the resulting segments.
Return an integer denoting the minimum possible total cost over all valid partitions.
Example 1
Input
s = "1010", enc_cost = 2, flat_cost = 1Output
6Splitting into four single-character segments gives costs 2, 1, 2, and 1, for a minimum total cost of 6.
Example 2
Input
s = "1010", enc_cost = 3, flat_cost = 10Output
12Splitting into two segments "10" and "10" gives cost 6 for each segment, for a minimum total cost of 12.
Constraints
- 1 <= s.length <= 10^5
- s consists only of '0' and '1'.
- 1 <= encCost, flatCost <= 10^5