Valid palindrome after deleting at most k characters

Return whether a string can become a palindrome by deleting at most k characters. Relate it to the longest palindromic subsequence and give the time and space of your solution.