Practice/Meta/Leetcode 1216. Valid Palindrome III

Leetcode 1216. Valid Palindrome III

CodingMust

Problem

You are given a string s and an integer k. Your task is to determine whether it's possible to transform the string into a palindrome by removing at most k characters.

A palindrome is a string that reads the same forwards and backwards. You can remove any characters from the string (not necessarily consecutive), and you want to check if the remaining characters can form a palindrome.

Return true if you can create a palindrome by deleting at most k characters, otherwise return false.

Requirements

1. Determine if removing up to k characters can make the string a palindrome
2. Characters can be removed from any position in the string
3. The remaining characters must maintain their relative order
4. Return a boolean indicating whether the transformation is possible

Constraints

• 1 ≤ s.length ≤ 1000
• s consists of lowercase English letters only
• 0 ≤ k ≤ s.length
• Expected time complexity: O(n²) where n is the length of the string
• Expected space complexity: O(n²)

Examples

Example 1:

Input: s = "abca", k = 1 Output: true Explanation: We can delete either 'b' to get "aca" or delete 'c' to get "aba", both are palindromes.

Example 2:

Input: s = "racecar", k = 0 Output: true Explanation: The string is already a palindrome, no deletions needed.

Example 3:

Input: s = "abcde", k = 1 Output: false Explanation: Even with 1 deletion, we cannot form a palindrome. We would need at least 3 deletions.

Example 4:

Input: s = "programming", k = 5 Output: true Explanation: We can remove 5 characters to form a palindrome like "rgmgr" or "rar".