Palindrome partitioning iii

String Dynamic Programming

62.1% acceptance

Feb 25, 2026

1209

You are given a string s containing lowercase letters and an integer k. You need to : First, change some characters of s to other lowercase English letters. Then divide s into k non-empty disjoint substrings such that each substring is a palindrome. Return the minimal number of characters that you need to change to divide the string.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn palindrome_partition(s: String, k: i32) -> i32 {
    let n = s.len();
    let k = k as usize;
    let s: Vec<u8> = s.bytes().collect();

    // cost[i][j] = min changes to make s[i..=j] a palindrome
    let mut cost = vec![vec![0i32; n]; n];
    for len in 2..=n {
      for i in 0..=n - len {
        let j = i + len - 1;
        cost[i][j] = cost[i + 1][j - 1] + if s[i] != s[j] { 1 } else { 0 };
      }
    }

    // dp[i][j] = min changes to partition s[0..=i] into j palindromes
    let mut dp = vec![vec![i32::MAX; k + 1]; n];
    for i in 0..n {
      dp[i][1] = cost[0][i];
    }

    for parts in 2..=k {
      for i in parts - 1..n {
        for mid in parts - 2..i {
          if dp[mid][parts - 1] != i32::MAX {
            let val = dp[mid][parts - 1] + cost[mid + 1][i];
            dp[i][parts] = dp[i][parts].min(val);
          }
        }
      }
    }
    dp[n - 1][k]
  }
}