Minimum Cost to Partition a Binary String - Solution & Explanation

Problem Overview: You are given a binary string and must split it into one or more contiguous partitions such that the total cost of all partitions is minimized. The cost of a segment depends on the imbalance of characters inside it, so the goal is to choose split points that minimize the cumulative cost across the entire string.

Approach 1: Pure Recursion (Brute Force) (Time: O(n^3), Space: O(n))

The most direct way is to try every possible partition of the string. For a starting index i, iterate over every possible end index j, treat s[i..j] as one segment, compute its cost, and recursively solve the remaining substring starting from j + 1. The recursion explores the full decision tree of possible partitions. Because each segment cost may require scanning the substring, the total time grows to O(n^3). This approach clearly shows the structure of the problem but becomes impractical for large strings.

Approach 2: Recursion with Prefix Sum Optimization (Time: O(n^2), Space: O(n))

The expensive part of the brute force solution is repeatedly recomputing statistics for each substring. A prefix sum array solves this by storing the cumulative count of '1's up to each position. With prefix sums, the number of ones in any substring can be computed in O(1). Since the substring length is known, the number of zeros is derived immediately. This allows you to compute the cost of any segment instantly while still exploring partition choices recursively. The recursion still tries all split points, but substring evaluation becomes constant time, reducing complexity to about O(n^2).

Approach 3: Divide and Conquer with Memoization (Time: O(n^2), Space: O(n))

The recursive formulation naturally overlaps: the minimum cost from index i is recomputed many times. Memoizing results for each starting index removes this redundancy. Store the minimum cost for each suffix of the string and reuse it whenever the recursion revisits that state. Combined with prefix sums, each state processes possible split points in a single loop. This pattern blends divide and conquer with dynamic programming over a string. The result is a practical O(n^2) algorithm that works efficiently within typical constraints.

Recommended for interviews: Start by explaining the brute force recursive partition idea because it demonstrates clear reasoning about how splits affect total cost. Then introduce prefix sums to eliminate repeated substring scans and add memoization to remove overlapping work. Interviewers typically expect the optimized recursive solution with prefix sums, since it shows both algorithmic insight and practical performance improvements.