Problem
Given a string s
and an integer k
, return true
if s
is a k
-palindrome.
A string is k
-palindrome if it can be transformed into a palindrome by removing at most k
characters from it.
Examples
Example 1:
|
|
Example 2:
|
|
Solution
Method 1 - Two Pointer Technique
To determine if a string can be transformed into a palindrome by deleting at most k
characters, we can use a two-pointer approach to count the mismatches from both ends of the string towards the centre. If we encounter more than k
mismatches, the answer is False
. Otherwise, it is True
.
Approach
- Use two pointers, one starting from the beginning (
left
) and the other from the end (right
) of the string. - While the
left
pointer is less than theright
pointer:- If the characters at the
left
andright
pointers are the same, move both pointers towards the centre. - If the characters are not the same, increment a mismatch counter and consider the following two scenarios:
- Skip the character at the
left
pointer and move it towards the right. - Skip the character at the
right
pointer and move it towards the left. - If either scenario results in a valid palindrome within the allowed
k
deletions, continue; otherwise, returnFalse
.
- Skip the character at the
- If the characters at the
- If the number of mismatches is less than or equal to
k
, returnTrue
.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n * k)
wheren
is the length of the string andk
is the maximum number of deletions allowed. - 🧺 Space complexity:
O(1)
for the two-pointer approach.