Minimum insertion steps to make a string palindrome

String Dynamic Programming

73.7% acceptance

Feb 25, 2026

5560

Given a string s. In one step you can insert any character at any index of the string. Return the minimum number of steps to make s palindrome. A Palindrome String is one that reads the same backward as well as forward.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_insertions(s: String) -> i32 {
    let b = s.as_bytes();
    let n = b.len();
    // dp[i][j] = min insertions to make s[i..=j] palindrome
    let mut dp = vec![vec![0i32; n]; n];
    for len in 2..=n {
      for i in 0..=n - len {
        let j = i + len - 1;
        if b[i] == b[j] {
          dp[i][j] = dp[i + 1][j - 1];
        } else {
          dp[i][j] = dp[i + 1][j].min(dp[i][j - 1]) + 1;
        }
      }
    }
    dp[0][n - 1]
  }
}