Valid Palindrome 3 - Is string palindrome after deleting at most k chars

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:

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

Example 2:

Input: s = "abbababa", k = 1
Output: true

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

1. Use two pointers, one starting from the beginning (left) and the other from the end (right) of the string.
2. While the left pointer is less than the right pointer:
   • If the characters at the left and right 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, return False.
3. If the number of mismatches is less than or equal to k, return True.

Code

Java

public class Solution {
    public boolean isValidPalindrome(String s, int k) {
        return isValidPalindromeHelper(s, 0, s.length() - 1, k);
    }

    private boolean isValidPalindromeHelper(String s, int left, int right, int k) {
        if (k < 0) {
            return false;
        }
        while (left < right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                return isValidPalindromeHelper(s, left + 1, right, k - 1) ||
                    isValidPalindromeHelper(s, left, right - 1, k - 1);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "waterrfetawx";
        int k = 2;
        System.out.println(solution.isValidPalindrome(s, k)); // Output: true
    }
}

Python

class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        return self._isValidPalindromeHelper(s, 0, len(s) - 1, k)

    def _isValidPalindromeHelper(self, s: str, left: int, right: int, k: int) -> bool:
        if k < 0:
            return False
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                return self._isValidPalindromeHelper(s, left + 1, right, k - 1) or \
                    self._isValidPalindromeHelper(s, left, right - 1, k - 1)
        return True

Complexity

• ⏰ Time complexity: O(n * k) where n is the length of the string and k is the maximum number of deletions allowed.
• 🧺 Space complexity: O(1) for the two-pointer approach.