K-Palindromes | Dynamic Programming Tutorials | Part 21

Hello guys, welcome back to “code with asharam”. This is part 21 of my dynamic programming tutorials. I will discuss “K-Palindromes” this time. If at any moment it feels like that things are going over your head, then, I advice to go through all the last tutorials. Even after that if you are stuck somewhere, then, feel free to leave a comment or send me a mail. I will answer your query as soon as possible. This problem is not much hard but its solutions are really interesting. It can have 2 efficient solutions and both are based on the problems we have already discussed. I will discuss both solutions in this tutorial. So, without any further delay, let’s take a dive into deep oceans of dynamic programming.

K-Palindromes

A string is called K-Palindrome if it can be made a palindrome by removing atmost k characters. Given a string S of length n, your task is to check whether S can be a K-palindrome or not.

Give it a try on your own before moving forward

Similarity to Minimum edit distance

So, what is the first thought that comes to your mind after hearing the word palindrome? Most obvious answer will be S = reverse(S). Now, as mentioned in the question we can remove atmost k characters from S to make S palindrome, i.e., to make S = reverse(S). This statement is similar to the problem edit distance but this time only delete operation is allowed. One more important fact to notice is if I remove ith character from S, then, (n-i)th character should also be removed from reverse(S) as they both are same things. This means that unlike original edit distance problem, reverse(S) (second string) is not fixed this time. We don’t need to worry about it as we can simply allow delete operation in both strings to counter this little problem. Also, we have to increase our atmost removal count to (2*k) as for every ith character removed in S, we have to remove (n-i)th character from reverse(S) afterwards.
Let’s try to make string S and S’ = reverse(S) equal by starting from their last (i and j respectively at any instance) character. Now, you can see that we only have these 2 possibilities:

  1. S[i] = S[j]: we cannot remove ith and jth character of S ans S’.
  2. S[i] != S[j]: Either we can remove ith character from S or we can remove jth character from the S’. In this case, our removal count will increase by 1.

Also it is clear if i=0, i.e., S is an empty string, then, we have to remove all the characters, i.e., j characters from S’ and vice versa. So, let’s see how our algorithm looks like till now:

edit(i, j) = max(i, j) if min(i, j) = 0
             edit(i-1, j-1) if S[i]==S'[j],
             1 + min(edit(i-1, j),
                     edit(i, j-1)) Otherwise

isK_Palindrome = edit(n, n) <= 2*k

As you can see that this recursive relation is exactly similar to the one we have used for edit distance. This is an exponential relation due to overlapping of sub problems and hence, we have to use a 2-d array to store result of all the n2 distinct function calls possible. Let’s see how our final algorithm looks like:

edit(i, j) = max(i, j) if min(i, j) = 0
             edit(i-1, j-1) if S[i]==S'[j],
             dp[i][j] if already computed, 
             dp[i][j] = 1 + min(edit(i-1, j),
                                edit(i, j-1)) Otherwise

isK_Palindrome = 2*k >= edit(n, n)

This was one of the two methods to solve K-Palindromes problem. Let’s now move to another method.

Similarity to Longest Palindromic subsequence

We can remove atmost k characters to make S a palindrome. So, let’s find out the minimum number of characters which have to be removed to make S a palindrome. If this is greater than k, then, S is not a K-Palindrome. Now, since we have to remove minimum number of character, hence, it means that whatever left will be the longest palindromic subsequence of S. Ultimately, the problem is reduced to finding the length of longest palindromic subsequence. I will directly use the relation used in lps tutorial. So, please read that before moving forward.

lps(i, j) = 1 if i=j
            2 if s[i]=s[j] and i+1 = j
            stored[i][j] if array have stored value
            stored[i][j] = 2 + lps(i+1, j-1) if s[i] == s[j]
            stored[i][j] = max(lps(i+1, j), lps(i, j-1)) otherwise

characterRemoved = n - lps(1, n)
isK_Palindrome = k >= characterRemoved

So, our algorithm writing is finished finally. Now, only task left is to write a beautiful code for these beautiful algorithms.

Code

#include <bits/stdc++.h>

using namespace std;

#define MAX 1001

int dp[MAX][MAX], stored[MAX][MAX];

int edit(int i, int j, string S, string revS)
{
    if (min(i, j) == 0) return max(i, j);

    if (S[i-1]==revS[j-1]) return edit(i-1, j-1, S, revS);

    if (dp[i][j] != -1) return dp[i][j];

    return dp[i][j] = 1 + min(edit(i-1, j, S, revS),
                              edit(i, j-1, S, revS));
}

int lps(int i, int j, string S)
{
    if (i==j) return 1;

    if (i+1==j && S[i-1]==S[j-1]) return 2;

    if (stored[i][j] != -1) return stored[i][j];

    if (S[i-1]==S[j-1]) return stored[i][j] = 2 + lps(i+1, j-1, S);

    return stored[i][j] = max(lps(i+1, j, S), lps(i, j-1, S));
}

int main()
{
    memset(dp, -1, sizeof(dp));
    memset(stored, -1, sizeof(stored));

    string S = "abcdecba";
    int k = 2, n = S.length();
    string revS = S;
    reverse(revS.begin(), revS.end());


    cout << (edit(n, n, S, revS) <= 2*k) << endl;
    cout << (n - lps(1, n, S) <= k) << endl;

    /*output is 1 in both case as we can remove
      "de" from S to make it a 2-palindrome*/
}

Finally, we have solved K-Palindromes with time and space complexity of O(n2).
So, that’s it guys for today. I hope you would have enjoyed this tutorial. If you liked this tutorial, then, please follow my blog and share it with your friends. Meanwhile, don’t forget to solve XM.
You can subscribe to my YouTube channel for video tutorials on dynamic programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: