Practice/Meta/Leetcode 2330. Valid Palindrome IV

Leetcode 2330. Valid Palindrome IV

CodingMust

Problem

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

In other words, after deleting up to k characters from s, the remaining characters (in their original order) should form a palindrome.

This is equivalent to checking whether the longest palindromic subsequence of s has a length of at least n - k, where n is the length of the original string.

Requirements

1. Return true if a palindrome can be formed by deleting at most k characters
2. Return false otherwise
3. The remaining characters must maintain their original relative order
4. You don't need to return the actual palindrome, just whether it's possible

Constraints

• 1 ≤ s.length ≤ 1000
• 0 ≤ k ≤ s.length
• s consists of lowercase English letters only
• Target time complexity: O(n²)
• Target space complexity: O(n²) or O(n) with optimization

Examples

Example 1:

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

Example 2:

Input: s = "abcdecba", k = 1 Output: true Explanation: The longest palindromic subsequence is "abcecba" (length 7). Since we need at least n-k = 8-1 = 7 characters, and the LPS is exactly 7, we can form a palindrome.

Example 3:

Input: s = "abcdef", k = 2 Output: false Explanation: The longest palindromic subsequence has length 1 (any single character). We need at least 6-2 = 4 characters to remain, but the best we can do is 1.

Example 4:

Input: s = "abba", k = 1 Output: true Explanation: The string is already a palindrome of length 4, so removing up to 1 character still works.