Minimum changes to make k semi palindromes

Two Pointers String Dynamic Programming

36.1% acceptance

Feb 25, 2026

130

106

Given a string s and an integer k, partition s into k substrings such that the letter changes needed to make each substring a semi-palindrome are minimized. Return the minimum number of letter changes required. A semi-palindrome is a special type of string that can be divided into palindromes based on a repeating pattern. To check if a string is a semi-palindrome: Choose a positive divisor d of the string's length. d can range from 1 up to, but not including, the string's length. For a string of length 1, it does not have a valid divisor as per this definition. The string is considered a semi-palindrome if each group forms a palindrome.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_changes(s: String, k: i32) -> i32 {
    let s = s.as_bytes();
    let n = s.len();
    let k = k as usize;

    // cost[i][j] = min changes to make s[i..=j] a semi-palindrome
    let mut cost = vec![vec![0i32; n]; n];
    for i in 0..n {
      for j in i..n {
        let len = j - i + 1;
        if len == 1 {
          cost[i][j] = i32::MAX / 2;
          continue;
        }
        let mut best = i32::MAX / 2;
        for d in 1..len {
          if len % d != 0 { continue; }
          let mut c = 0i32;
          for g in 0..d {
            let group_len = len / d;
            let mut lo = 0usize;
            let mut hi = group_len - 1;
            while lo < hi {
              if s[i + g + lo * d] != s[i + g + hi * d] {
                c += 1;
              }
              lo += 1;
              hi -= 1;
            }
          }
          best = best.min(c);
        }
        cost[i][j] = best;
      }
    }

    // DP: dp[parts][end] = min cost for first (end+1) chars split into `parts` semi-palindromes
    const INF: i32 = i32::MAX / 2;
    let mut dp = vec![vec![INF; n]; k + 1];
    for j in 0..n {
      dp[1][j] = cost[0][j];
    }
    for parts in 2..=k {
      for j in 0..n {
        for split in 0..j {
          if dp[parts - 1][split] < INF {
            let c = dp[parts - 1][split].saturating_add(cost[split + 1][j]);
            if c < dp[parts][j] {
              dp[parts][j] = c;
            }
          }
        }
      }
    }
    dp[k][n - 1]
  }
}