Palindrome removal

Array Dynamic Programming

46.2% acceptance

Mar 31, 2026

318

No description available.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_moves(arr: Vec<i32>) -> i32 {
    let n = arr.len();
    let mut dp = vec![vec![0i32; n]; n];
    for i in 0..n {
      dp[i][i] = 1;
    }
    for len in 2..=n {
      for i in 0..=n - len {
        let j = i + len - 1;
        dp[i][j] = dp[i + 1][j] + 1; // remove arr[i] alone
        for k in i + 1..=j {
          if arr[k] == arr[i] {
            let right = if k + 1 <= j { dp[k + 1][j] } else { 0 };
            let left = if i + 1 <= k - 1 { dp[i + 1][k - 1] } else { 0 };
            // merge removal of arr[i] and arr[k] 
            dp[i][j] = dp[i][j].min(left.max(1) + right);
          }
        }
      }
    }
    dp[0][n - 1]
  }
}