K-Palindrome Problem Statement

Determine whether a given string str can be considered a K-Palindrome.

A string is considered a K-Palindrome if it can be transformed into a palindrome after removing up to ‘k’ characters.

Example:

Input:

str = "ababba", k = 3

Output:

True

Explanation:

If we remove one ‘b’ from the 3rd position, the string becomes "ababa", which is a palindrome. Thus, the output is True.

Constraints:

1

Question

Determine whether a given string str can be considered a K-Palindrome.

A string is considered a K-Palindrome if it can be transformed into a palindrome after removing up to ‘k’ characters.

str = "ababba", k = 3

True

If we remove one ‘b’ from the 3rd position, the string becomes "ababa", which is a palindrome. Thus, the output is True.

Accepted Answer

The problem is to determine whether a given string can be considered a K-Palindrome by removing up to 'k' characters.

Iterate through the string from both ends and check if characters match, if not increment removal count
If removal count is less than or equal to k, return True, else return False
Use dynamic programming to optimize the solution by storing subproblem results

Uber Software Engineer interview questions & answers