Validating K-Palindromes

From LeetCode:

Given a string s and an integer k, find out if the given string is a k-palindrome or not. A string is a k-palindrome if it can be transformed into a palindrome by removing at most k characters from it.

Input: s = "abcdeca", k = 2
Output: True # Remove 'b' and 'e'

We last encountered palindromes in Minimum Palindromic Partitions, a DP challenge that required to expand (leftward and rightward) from all possible midpoints in a string composed of palindromes.

In this problem, we’re dealing with a string s that may not have palindromic properties –– in the sense that it’s neither guaranteed to be a palindrome nor confirmed to be made up of palindromes. This means our tactic of expanding from midpoints to discover palindromes will be rather irrelevant. We’ll need a different strategy.

One thing to keep in mind about palindromes is that they remain the same in appearance after being reversed. For k-palindromes, could we perhaps draw some conclusions about them by comparing them to their reversed selves?

K-Palindromes and Reversed K-Palindromes

Suppose that s is "dxbyd". At first glance, we know that the longest palindromic subsequence of "dxbyd" is "dbd", but let’s think about what it takes to make s equivalent to its reverse, s[::-1]:

"""
original: "dxbyd" -> "dbd"
---------------------------
reversed: "dybxd" -> "dbd"
"""
# Total characters removed: 4
# Total characters removed from original: 2

We can obtain the longest common subsequence between s and s[::-1] by removing the "x" and "y" characters from both strings. This subsequence, "dbd", matches the longest palindromic subsequence we had in mind.

In total, we’ve deleted 4 characters and removed equal numbers of characters from both strings. It appears that s is indeed a k-palindrome string if k >= 2.

In some ways, the steps above might remind you of the Edit Distance problem as well as the Longest Common Subsequence problem. Both questions can be tied back to our current challenge, but since we don’t have all day, we’ll just examine the former.

Comparisons to the Edit Distance Problem

In the Edit Distance problem, we use DP to convert a string s1 into another string s2. In our current problem, we trim both s and s[::-1] to derive a common subsequence.

Let’s clarify a subtle difference here. Transforming a string s1 into another string s2 seems like a “unidirectional” operation. At each step, we can either:

• Option 1A: Append a character to s1
• Option 1B: Remove a character from s1
• Option 1C: Substitute a character in s1

Trimming both s and s[::-1] so that they match each other, on the other hand, appears to be a “bidirectional” operation. At each step, we can either:

• Option 2A: Remove a character from s
• Option 2B: Remove a character from s[::-1]

It turns out that adding a character to the original string (option 1A) exactly mirrors removing a character from the other string (option 2B). Suppose we had two strings, "ab" and "ba":

• Starting from "ab", we can convert "ab" into "b" and then append "a" to derive "ba".
• Starting from "ba", we can convert "b" into "ab" and then remove "a" to derive "ab".

Both operations are analogous to each other and fundamentally wrap around the same subproblem of converting between "ab" and "b".

In this light, our K-Palindrome problem is really just a twist on the Edit Distance problem that takes s and s[::-1] as parameters but doesn’t allow for character substitution (i.e. option 1C).

From Intuition to Code

Let’s build up a DP-based helper that will help us determine the number of deletes required to obtain the longest palindromic subsequence:

def delete_dist(a, b):

    # DP[i]:
    # - Delete distance between a[:i+1] and b[:j+1]
    # - Value of j determined by curr loop iteration
    # - Init state: b is empty
    DP = [i + 1 for i in range(len(a))]

    for j in range(len(b)):

        new_DP = DP[:]

        for i in range(len(a)):
            if a[i] == b[j]:
                new_DP[i] = (
                    # a[:i+1] -> b[:j+1] is the same as
                    # a[:i] -> b[:j]
                    DP[i-1] if i > 0 else j
                )
            else:
                new_DP[i] = min(
                    # a[:i+1] -> b[:j+1] is the minimum of:
                    # 1) a[:i] -> b[:j+1], remove a[i]
                    (new_DP[i-1] if i > 0 else j + 1) + 1,
                    # 2) b[:j] -> a[:i+1], remove b[j]
                    DP[i] + 1
                )

        DP = new_DP

    return DP[-1]

Some things to note:

• Handling cases where i < 0 can be tricky –– you just need to realise that i == -1 represents the empty string a[:0].
• In the above code, DP[i] includes the character at index i, but you can certainly dictate the semantics behind your own DP array. For instance, you could make DP[i] exclusive such that it only accounts for the characters before i. This way, you can also store j+1 into DP[0] to handle the subproblem where a is empty (i.e. a[:0]).
• For simplicity, you can always use a 2D array to track your DP results first and optimise for space later.

We can now use our DP-based helper to calculate the total number of character deletions between s and s[::-1]:

def is_k_palindrome(s, k):
    def delete_dist(a, b):
        # Run DP algorithm
        # ...

    return delete_dist(s, s[::-1]) <= 2 * k

If s is a k-palindrome, then the total number of deletions required to achieve the longest palindromic subsequence should be less than 2 * k. As mentioned earlier, the number of characters deleted in s will the same as the number of characters deleted in s[::-1] (i.e. half of the total number).

Given n characters in string s, our algorithm runs in O(n) space and O(n^2) time.

With that, we’ve solved the Validating K-Palindromes problem 🍓🏰🍎.

Full Solution

def is_k_palindrome(s, k):
    def delete_dist(a, b):
        DP = [i + 1 for i in range(len(a))]
        
        for j in range(len(b)):
            
            new_DP = DP[:]

            for i in range(len(a)):
                if a[i] == b[j]:
                    new_DP[i] = (
                        # a[:i] -> b[:j]
                        DP[i-1] if i > 0 else j
                    )
                    
                else:
                    new_DP[i] = min(
                        # a[:i] -> b[:j+1], remove a[i]
                        (new_DP[i-1] if i > 0 else j + 1) + 1,
                        # b[:j] -> a[:i+1], remove b[j]
                        DP[i] + 1
                    )
                    
            DP = new_DP
        
        return DP[-1]
    
    return delete_dist(s, s[::-1]) <= 2 * k