Given a binary string s and two integers encCost and flatCost, determine the minimum cost to partition s.

A string or substring can be evaluated as follows:

• If the segment contains no '1' characters, its cost is flatCost.

• If the segment contains at least one '1' character, its cost is $ ext{length} imes k imes$ encCost, where $ ext{length}$ is the length of the segment and $k$ is the number of '1' characters in it.

Additionally, whenever a segment has an even length, it can either be kept as a single unit with the cost calculated above, or divided into two equal contiguous halves. If divided, the total cost for that segment is the sum of the minimum costs of its two halves.

Return the minimum total cost required to process the entire string s.

Constraints:

• $1 \le$ s.length $\le 10^5$

• s consists only of '0' and '1'.

• $1 \le$ encCost, flatCost $\le 10^5$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.