Skip to main content
Back to problems
#1216
Hard Algorithms

Valid palindrome iii

String Dynamic Programming
49.1% acceptance
Mar 31, 2026
843
15

No description available.

Solution

Rust
Time O(n * m)
Space O(n * m)
LeetCode
solution.rs
impl Solution {
  pub fn is_valid_palindrome(s: String, k: i32) -> bool {
    let s: Vec<u8> = s.into_bytes();
    let n = s.len();
    let mut dp = vec![vec![0u16; 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;
        if s[i] == s[j] {
          dp[i][j] = dp[i + 1][j - 1] + 2;
        } else {
          dp[i][j] = dp[i + 1][j].max(dp[i][j - 1]);
        }
      }
    }
    (n as i32 - dp[0][n - 1] as i32) <= k
  }
}