Minimum cost to partition a binary string

String Divide and Conquer Prefix Sum

52.6% acceptance

Mar 16, 2026

You are given a binary string s and two integers encCost and flatCost. For a segment of length L containing X sensitive elements ('1's): - If X = 0, the cost is flatCost. - If X > 0, the cost is L * X * encCost. If a segment has even length, you may split it into two contiguous segments of equal length. The cost is the sum of costs of the resulting segments. Return the minimum possible total cost over all valid partitions.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(s: String, enc_cost: i32, flat_cost: i32) -> i64 {
    let bytes = s.as_bytes();
    let n = bytes.len();
    let enc = enc_cost as i64;
    let flat = flat_cost as i64;

    // Build prefix sums of '1's
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + if bytes[i] == b'1' { 1 } else { 0 };
    }

    // Memoization: cost(l, r) = min cost for segment s[l..r] (0-indexed, exclusive end)
    // A segment [l, r) has length r-l, ones = prefix[r] - prefix[l]
    // If ones == 0: cost = flat
    // If ones > 0: cost = (r-l) * ones * enc, but if length is even, can split into [l, mid) and [mid, r)
    // and take min.

    // Since splits always halve, the segment lengths are powers-of-2 divisors of the original.
    // Actually, the initial segment is the whole string, length n. We can split if even.
    // After splitting, each half can be split if its length is even. And so on recursively.
    // This forms a binary tree of segments.

    // The segments are always of the form [i * len, (i+1) * len) where len divides n by repeated halving.
    // Actually no: starting with [0, n), split to [0, n/2) and [n/2, n). Each can split further if even length.
    // So segment boundaries are dyadic intervals.

    // Memoize by (start, length). Use HashMap.
    use std::collections::HashMap;
    let mut memo: HashMap<(usize, usize), i64> = HashMap::new();

    fn solve(
      l: usize, len: usize, prefix: &[i64], enc: i64, flat: i64,
      memo: &mut HashMap<(usize, usize), i64>,
    ) -> i64 {
      if let Some(&v) = memo.get(&(l, len)) {
        return v;
      }
      let r = l + len;
      let ones = prefix[r] - prefix[l];
      let cost_unsplit = if ones == 0 {
        flat
      } else {
        len as i64 * ones * enc
      };

      let result = if len % 2 == 0 && len >= 2 {
        let half = len / 2;
        let split_cost = solve(l, half, prefix, enc, flat, memo)
          + solve(l + half, half, prefix, enc, flat, memo);
        cost_unsplit.min(split_cost)
      } else {
        cost_unsplit
      };

      memo.insert((l, len), result);
      result
    }

    solve(0, n, &prefix, enc, flat, &mut memo)
  }
}