Palindrome After a Few Erasures

Hard

You are given a string text and an integer budget. You may erase at most budget characters from the string, any characters at any positions; the remaining ones keep their order. Can you erase characters so that what is left reads the same forwards and backwards? Return True if you can and False otherwise.

Example 1

text='radkar', budget=1 → True

Erasing the "k" leaves the palindrome "radar".

Example 2

text='lever', budget=1 → False

The longest palindrome that can be kept is "eve", three letters long, so two letters must go while only one may be erased.

Example 3

text='noon', budget=1 → True

The string is already a palindrome, nothing has to be erased.

Constraints

1 ≤ text.length ≤ 1000
text consists of lowercase English letters only
1 ≤ budget ≤ text.length

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Shuffle by Cutting and Swapping Hard Ways to Cross Out Hard

Input

text='radkar', budget=1

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 105 tests on the server, hidden ones included.