I had phone screen round in November and was asked [Valid Palidrome || ](https://leetcode.com/problems/valid-palindrome-ii/).\nI was quite quick to present the O(n) time & space solution and maybe that\'s why interviewer went with the follow-up instead of 2nd question.\n\nFollow up question was `with max k deletions if we can make a string palindrome or not`.\n\nEg - `abceda`, k =  2 , **Output** - `False`\n`abccda`, k = 2, **Output** - `True`\n\n**Solution** - I followed the same approach but then suddenly realized this is DP question and was surpsied considering fb dont ask one.\n\nMy approach was to start from beginning and end towards the center, and whenever there is a mismatch, spin off two branches from there and reduce deletion count by 1. When we reach middle/or end < start, then we check if k >= 0, if yes, then we return `True` else `False`. We can short circuit by checking if k is negative and return `False` right away.\nThis would be O(2^n) in worst case, with DP, it could go to O(n^3) [I was storing start, end, index  as the key]\n\nYour thoughts? Could it be brought down to O(n^2) ?\n

I had phone screen round in November and was asked Valid Palidrome || .\nI was quite quick to present the O(n) time & space solution and maybe that\'s why inter