#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)
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
}
}