Valid Palindrome III

Given a string s and integer k, determine whether you can delete at most k characters to make s a palindrome. This essentially asks whether the longest palindromic subsequence has length ≥ n−k, typically solved with an O(n^2) dynamic programming approach.