3864. Minimum Cost to Partition a Binary String

HardStringDivide and ConquerPrefix Sum

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a binary string s and two integers encCost and flatCost.

For each index i:

s[i] = '1' means the ith element is sensitive.
s[i] = '0' means the ith element is not sensitive.

The string must be partitioned into segments. At the start, the entire string is treated as a single segment.

For a segment of length L that contains X sensitive elements, the cost is computed as follows:

If X = 0 (no sensitive elements), the cost is flatCost.
If X > 0 (at least one sensitive element), the cost is L * X * encCost.

You are allowed to perform splits under the following rule:

If a segment has even length, you may split it into two contiguous segments of equal length. The cost of doing this split is the sum of the costs of the two resulting segments.

Each resulting segment can again be split following the same rule, as long as it has even length.

Return an integer denoting the minimum possible total cost over all valid partitions of the string.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Divide and Conquer / Tree DP?

This problem maps to Divide and Conquer / Tree DP through a short path in the full flowchart.

Recursively splits even-length segments at the midpoint, comparing keep-whole cost against sum of optimal two halves.

Open in Flowchart

Intuition

The key observation is that a segment can only be split in one specific way: an even-length segment can be divided into exactly two equal halves. This means the set of all possible segments is limited and follows a clear recursive structure — each segment either stays whole, or breaks into its left half and right half, which in turn may break again.

Because of this, for any segment we face a simple binary choice:

Keep it as a single segment and pay its direct cost. This cost depends on how many sensitive elements it contains: if there are sensitive elements (X > 0), the cost is L * X * encCost; otherwise it is flatCost.
Split it into two equal halves (only possible when the length is even) and pay the sum of the optimal costs of the two halves.

The best answer for a segment is simply the minimum of these two options. Since the cost of splitting depends on solving the same problem for smaller halves, this naturally leads to a recursive formulation: define a function over an interval [l, r) that returns the minimum cost for that portion of the string.

To compute the direct cost of any interval quickly, we need to know how many sensitive elements it contains. Instead of counting them every time, we precompute a prefix sum array, so the number of sensitive elements in [l, r) is just pre[r] - pre[l] in constant time.

Putting it together: we recurse on the whole string [0, n). At each interval we compute its direct cost, and if the length is even, we also try splitting at the midpoint m = (l + r) // 2 and compare. Taking the smaller value at every step guarantees the overall minimum possible total cost.

Pattern Learn more about Divide and Conquer and Prefix Sum patterns.

Solution Approach

Solution 1: Recursion

We define a function dfs(l, r) that represents the minimum cost for the interval [l, r) of string s. We use a prefix sum array pre to quickly calculate the number of sensitive elements x in the interval [l, r), which lets us compute the direct cost without splitting in constant time.

The calculation process of function dfs(l, r) is as follows:

Calculate the number of sensitive elements x in the interval [l, r) using x = pre[r] - pre[l].
Calculate the cost without splitting: if x > 0, the cost is (r - l) * x * encCost; if x = 0, the cost is flatCost.
If the interval length r - l is even, we can try to split it into two equal segments. Let m = (l + r) // 2, then the cost after splitting is dfs(l, m) + dfs(m, r). We take the smaller value between the non-split cost and the split cost.

The answer is dfs(0, n), where n is the length of string s.

Data structures and patterns used:

Prefix sum array pre: We build pre so that pre[i] stores the number of sensitive elements ('1's) in the first i characters. This is constructed by iterating over s and accumulating pre[i] = pre[i - 1] + int(c). With this, the count of sensitive elements in any interval [l, r) is pre[r] - pre[l].
Recursion (divide and conquer): The function dfs explores the two choices — keep the segment whole or split it into halves — and returns the minimum. Because each even-length segment splits into exactly two equal halves, the recursion naturally mirrors the structure of valid partitions.

The time complexity is O(n × log n), where n is the length of string s. This is because each level of the recursion processes O(n) total work across all segments, and the recursion depth is O(log n) since lengths are halved each time. The space complexity is O(n) for the prefix sum array, plus O(log n) for the recursion stack.

Example Walkthrough

Let's trace through a small example to see how the recursive solution works.

Input:

s = "1001"
encCost = 2
flatCost = 5

Step 1: Build the prefix sum array

We accumulate the count of sensitive elements ('1's):

Index `i`	0	1	2	3	4
`pre[i]`	0	1	1	1	2

So the number of sensitive elements in any interval [l, r) is pre[r] - pre[l]. For example, the whole string [0, 4) has pre[4] - pre[0] = 2 sensitive elements.

Step 2: Start the recursion with dfs(0, 4)

The whole string "1001" has length 4 and x = 2 sensitive elements.

Cost without splitting: since x > 0, cost = (4 - 0) * 2 * 2 = 16.
Length is even, so we try splitting at m = (0 + 4) // 2 = 2, giving us dfs(0, 2) + dfs(2, 4).

Step 3: Evaluate the left half dfs(0, 2) → segment "10"

x = pre[2] - pre[0] = 1 sensitive element.
Cost without splitting: (2 - 0) * 1 * 2 = 4.
Length is even, split at m = 1 → dfs(0, 1) + dfs(1, 2).
- dfs(0, 1) → "1": x = 1, cost = 1 * 1 * 2 = 2 (length odd, no split).
- dfs(1, 2) → "0": x = 0, cost = flatCost = 5 (length odd, no split).
- Split cost = 2 + 5 = 7.
Compare: min(4, 7) = 4. So dfs(0, 2) = 4.

Step 4: Evaluate the right half dfs(2, 4) → segment "01"

x = pre[4] - pre[2] = 1 sensitive element.
Cost without splitting: (4 - 2) * 1 * 2 = 4.
Length is even, split at m = 3 → dfs(2, 3) + dfs(3, 4).
- dfs(2, 3) → "0": x = 0, cost = flatCost = 5.
- dfs(3, 4) → "1": x = 1, cost = 1 * 1 * 2 = 2.
- Split cost = 5 + 2 = 7.
Compare: min(4, 7) = 4. So dfs(2, 4) = 4.

Step 5: Combine back at dfs(0, 4)

Split cost = dfs(0, 2) + dfs(2, 4) = 4 + 4 = 8.
Compare with the non-split cost: min(16, 8) = 8.

Result: The minimum possible total cost is 8, achieved by splitting the string into the two halves "10" and "01", keeping each as a whole segment.

This walkthrough shows the core idea in action: at every interval we weigh "keep whole" against "split into halves," and the prefix sum lets us compute each segment's direct cost instantly.

Solution Implementation

1class Solution:
2    def minCost(self, s: str, encCost: int, flatCost: int) -> int:
3        # prefix[i] holds the sum of digits for s[0:i],
4        # so the count of '1's in s[left:right] is prefix[right] - prefix[left].
5        n = len(s)
6        prefix = [0] * (n + 1)
7        for i, char in enumerate(s, 1):
8            prefix[i] = prefix[i - 1] + int(char)
9
10        def dfs(left: int, right: int) -> int:
11            # Number of '1's within the current segment s[left:right].
12            ones_count = prefix[right] - prefix[left]
13
14            # Cost of encoding the whole segment as a single block:
15            # - if it contains any '1', cost is length * ones_count * encCost
16            # - if it is all '0's, the segment is "flat", costing flatCost
17            result = (right - left) * ones_count * encCost if ones_count else flatCost
18
19            # Only segments of even length can be split into two equal halves.
20            if (right - left) % 2 == 0:
21                mid = (left + right) // 2
22                # Compare keeping the segment whole vs. splitting it in two.
23                result = min(result, dfs(left, mid) + dfs(mid, right))
24
25            return result
26
27        # Solve for the entire string.
28        return dfs(0, n)
29

1class Solution {
2    // Prefix sum array: prefixSum[i] holds the number of '1' characters in s[0..i-1]
3    private int[] prefixSum;
4    // Cost factor applied to non-uniform (mixed) segments
5    private int encCost;
6    // Fixed cost applied to a segment consisting entirely of '0's
7    private int flatCost;
8
9    public long minCost(String s, int encCost, int flatCost) {
10        int n = s.length();
11        this.encCost = encCost;
12        this.flatCost = flatCost;
13
14        // Build the prefix sum array of digit values
15        prefixSum = new int[n + 1];
16        for (int i = 1; i <= n; ++i) {
17            prefixSum[i] = prefixSum[i - 1] + (s.charAt(i - 1) - '0');
18        }
19
20        // Compute the minimum cost for the entire string
21        return dfs(0, n);
22    }
23
24    /**
25     * Recursively computes the minimum cost for the segment [left, right).
26     *
27     * @param left  inclusive start index of the segment
28     * @param right exclusive end index of the segment
29     * @return the minimum cost to process this segment
30     */
31    private long dfs(int left, int right) {
32        // Number of '1' characters within the current segment
33        int onesCount = prefixSum[right] - prefixSum[left];
34
35        // Base cost for keeping the segment as a whole:
36        // - if it contains any '1', use length * onesCount * encCost
37        // - otherwise (all zeros), use the fixed flatCost
38        long res = onesCount != 0
39                ? (long) (right - left) * onesCount * encCost
40                : flatCost;
41
42        // If the segment length is even, try splitting it into two equal halves
43        if ((right - left) % 2 == 0) {
44            int mid = (left + right) >> 1;
45            res = Math.min(res, dfs(left, mid) + dfs(mid, right));
46        }
47
48        return res;
49    }
50}
51

1class Solution {
2public:
3    long long minCost(string s, int encCost, int flatCost) {
4        int n = s.size();
5
6        // prefix[i] stores the count of '1' characters in s[0..i-1].
7        // This lets us query the number of set bits in any range in O(1).
8        std::vector<int> prefix(n + 1);
9        for (int i = 1; i <= n; ++i) {
10            prefix[i] = prefix[i - 1] + (s[i - 1] - '0');
11        }
12
13        // dfs computes the minimum cost to encode the substring s[left..right-1].
14        //
15        // Two options are compared:
16        //   1) Encode the whole block directly. If it contains any '1', the cost
17        //      is (length * onesCount * encCost); otherwise it is a single flatCost.
18        //   2) If the block length is even, split it into two equal halves and
19        //      recursively solve each half, taking the cheaper combined result.
20        auto dfs = [&](this auto&& dfs, int left, int right) -> long long {
21            // Number of '1's within the current block [left, right).
22            int onesCount = prefix[right] - prefix[left];
23
24            // Cost of encoding this block as a single unit.
25            long long result = onesCount
26                                   ? 1LL * (right - left) * onesCount * encCost
27                                   : flatCost;
28
29            // Only an even-length block can be evenly divided in two.
30            if ((right - left) % 2 == 0) {
31                int mid = (left + right) >> 1;
32                result = std::min(result, dfs(left, mid) + dfs(mid, right));
33            }
34
35            return result;
36        };
37
38        // Solve for the entire string [0, n).
39        return dfs(0, n);
40    }
41};
42

1// Prefix sum array storing cumulative count of '1' characters
2let prefixOnes: number[];
3// Cost multiplier applied when encoding a non-empty segment
4let encodeCost: number;
5// Flat cost applied when a segment contains only '0' characters
6let flatSegmentCost: number;
7
8/**
9 * Recursively computes the minimum cost for the substring covering [left, right).
10 *
11 * Two options are considered:
12 *   1. Treat the whole range as a single block.
13 *      - If it contains at least one '1', the cost is (length * onesCount * encodeCost).
14 *      - Otherwise (all zeros), the cost is flatSegmentCost.
15 *   2. If the range length is even, split it into two equal halves and
16 *      recurse on each, taking whichever total is smaller.
17 *
18 * @param left  Inclusive left boundary index.
19 * @param right Exclusive right boundary index.
20 * @returns Minimum cost to encode the range [left, right).
21 */
22function dfs(left: number, right: number): number {
23    // Number of '1' characters within the current range
24    const onesCount = prefixOnes[right] - prefixOnes[left];
25
26    // Cost of treating the entire range as one block
27    let result = onesCount
28        ? (right - left) * onesCount * encodeCost
29        : flatSegmentCost;
30
31    // Attempt to split into two equal halves when the length is even
32    if ((right - left) % 2 === 0) {
33        const mid = (left + right) >> 1;
34        result = Math.min(result, dfs(left, mid) + dfs(mid, right));
35    }
36
37    return result;
38}
39
40/**
41 * Computes the minimum cost to encode the binary string `s`.
42 *
43 * @param s         Binary string consisting of '0' and '1' characters.
44 * @param encCost   Per-unit encoding cost multiplier for non-empty segments.
45 * @param flatCost  Flat cost charged for all-zero segments.
46 * @returns The minimum total encoding cost.
47 */
48function minCost(s: string, encCost: number, flatCost: number): number {
49    const n = s.length;
50
51    // Build the prefix sum of '1' counts: prefixOnes[i] holds the number of
52    // '1' characters in the first i characters of s.
53    prefixOnes = new Array(n + 1).fill(0);
54    for (let i = 1; i <= n; i++) {
55        prefixOnes[i] = prefixOnes[i - 1] + Number(s[i - 1]);
56    }
57
58    // Store costs in module-level variables so dfs can access them.
59    encodeCost = encCost;
60    flatSegmentCost = flatCost;
61
62    // Solve for the full string range [0, n).
63    return dfs(0, n);
64}
65

Time and Space Complexity

Time Complexity: O(n), where n is the length of string s.

First, building the prefix sum array pre takes O(n) time.

For the dfs function, the recursion only splits the interval into two equal halves when the length r - l is even, and the splitting point is exactly the midpoint m = (l + r) // 2. This forms a recursion tree that resembles a binary tree built over the string.

At each level of recursion, the total length covered by all intervals at that level sums to n. The work done at each node (computing x, res, etc.) is O(1). The number of levels is at most O(log n), but the key observation is that the total number of distinct intervals processed is bounded by O(n).

Specifically, since each interval can only be split into two halves at the exact midpoint, the recursion tree only branches on power-of-two aligned segments. The total number of nodes across the entire recursion is O(n), because the intervals at each level partition (a subset of) the original range without overlap, and the recursion depth is O(log n) with each level contributing at most O(n) total intervals counted overall as O(n). Thus the overall time complexity is O(n).
Space Complexity: O(n), where n is the length of string s.

The prefix sum array pre requires O(n) space. The recursion stack depth is at most O(log n) since the interval is halved at each recursive step. Therefore, the dominant term is the prefix array, giving an overall space complexity of O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Split Rule and Computing the Cost at the Wrong Granularity

The most common mistake is misreading when and how a segment can be split. The rule states that a segment can only be split if it has even length, and the split must produce two contiguous halves of equal length. Developers often make one of these errors:

Splitting at an arbitrary index (e.g., trying every possible mid from left+1 to right-1) instead of only at the exact midpoint mid = (left + right) // 2. This violates the "equal length" requirement and explores invalid partitions, producing a wrong (often too-low) answer.
Attempting to split odd-length segments. If you forget the (right - left) % 2 == 0 check, you'll generate unequal halves and potentially recurse forever or compute illegal states.

Solution: Always guard the split with an even-length check and only ever cut at the exact midpoint.

if (right - left) % 2 == 0:          # only even-length segments are splittable
    mid = (left + right) // 2        # split must be at the exact midpoint
    result = min(result, dfs(left, mid) + dfs(mid, right))

Pitfall 2: Confusing the Two Cost Formulas (Flat vs. Encoded)

It's easy to apply the wrong cost branch. The flat cost (flatCost) applies only when a segment has zero sensitive elements. As soon as X > 0, the cost becomes L * X * encCost. A frequent bug is writing something like:

# WRONG: uses length * encCost regardless of ones_count, or adds flatCost too
result = (right - left) * encCost

or accidentally taking min(flatCost, L * X * encCost) even when X > 0, which silently allows the flat cost where it isn't permitted.

Solution: Branch strictly on whether ones_count is zero:

ones_count = prefix[right] - prefix[left]
result = (right - left) * ones_count * encCost if ones_count else flatCost

The ternary ensures flatCost is used exclusively for all-zero segments and the encoded formula is used otherwise.

Pitfall 3: Off-by-One Errors with the Prefix Sum and Half-Open Intervals

The recursion uses half-open intervals [left, right), and the prefix array is 1-indexed so that prefix[r] - prefix[l] counts '1's in s[l:r]. Mixing this up — for example using inclusive intervals [left, right], sizing prefix as n instead of n + 1, or computing length as right - left + 1 — leads to counting elements twice, index-out-of-range errors, or an incorrect segment length.

Solution: Keep the conventions consistent everywhere:

prefix = [0] * (n + 1)               # size n + 1 for 1-indexed prefix sums
for i, char in enumerate(s, 1):      # enumerate starting at 1
    prefix[i] = prefix[i - 1] + int(char)

# length is (right - left), NOT (right - left + 1) for half-open intervals
length = right - left
ones_count = prefix[right] - prefix[left]

Pitfall 4: Redundant Recomputation Without Memoization

Although the natural recursion here visits each distinct segment only once (because splits always go to the exact midpoint, the set of reachable intervals forms a balanced binary tree of size O(n)), developers sometimes "optimize" by trying multiple split points or rewrite the recursion in a way that revisits the same (left, right) repeatedly. Once you deviate from the midpoint-only split, the state space can explode and the same interval may be solved many times.

Solution: Stick to the midpoint-only recursion, which keeps the total number of unique calls at O(n). If you ever generalize the splitting logic, add memoization keyed on (left, right):

from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(left: int, right: int) -> int:
    ...

This guarantees each interval is computed at most once, preserving the O(n × log n) overall time complexity.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know