Palindrome partitioning ii

String Dynamic Programming

36.6% acceptance

Jan 12, 2026

5907

157

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_cut(s: String) -> i32 {
    let n = s.len();
    let chars: Vec<char> = s.chars().collect();
    
    // dp[i] = minimum cuts needed for substring s[0..i]
    let mut dp = vec![0; n];
    
    // is_palindrome[i][j] = true if s[i..=j] is palindrome
    let mut is_palindrome = vec![vec![false; n]; n];
    
    for i in 0..n {
      let mut min_cuts = i as i32;
      
      for j in 0..=i {
        if chars[j] == chars[i] && (i - j <= 2 || is_palindrome[j + 1][i - 1]) {
          is_palindrome[j][i] = true;
          min_cuts = if j == 0 { 0 } else { min_cuts.min(dp[j - 1] + 1) };
        }
      }
      
      dp[i] = min_cuts;
    }
    
    dp[n - 1]
  }
}