Determine if a given string is a k-palindrome

Question

I'm trying to solve the following interview practice question:

A k-palindrome is a string which transforms into a palindrome on removing at most k characters.

Given a string S, and an integer K, print "YES" if S is a k-palindrome; otherwise print "NO".

Constraints:

S has at most 20,000 characters.
0 <= k <= 30

Sample Test Cases:

Input - abxa 1 
Output - YES 

Input - abdxa 1 
Output - NO

My approach I've decided is going to be taking all possible String combinations of length s.length - k or greater, i.e. "abc" and k = 1 -> "ab" "bc" "ac" "abc" and checking if they are palindromes. I have the following code so far, but can't seem to figure out a proper way to generate all these string combinations in the general case:

public static void isKPalindrome(String s, int k) {
  // Generate all string combinations and call isPalindrome on them,
  //   printing "YES" at first true 
}

private static boolean isPalindrome(String s) {
    char[] c = s.toCharArray()
    int slow = 0;
    int fast = 0;
    Stack<Character> stack = new Stack<>();
    while (fast < c.length) {
        stack.push(c[slow]);
        slow += 1;
        fast += 2;
    }
    if (c.length % 2 == 1) {
        stack.pop();
    }
    while (!stack.isEmpty()) {
        if (stack.pop() != c[slow++]) {
            return false;
        }
    }
    return true;
}

Can anyone figure out a way to implement this, or perhaps demonstrate a better way?

Answer 1

I think there is a better way

package se.wederbrand.stackoverflow;

public class KPalindrome {
    public static void main(String[] args) {
        KPalindrome kPalindrome = new KPalindrome();
        String s = args[0];
        int k = Integer.parseInt(args[1]);
        if (kPalindrome.testIt(s, k)) {
            System.out.println("YES");
        }
        else {
            System.out.println("NO");
        }
    }

    boolean testIt(String s, int k) {
        if (s.length() <= 1) {
            return true;
        }

        while (s.charAt(0) == s.charAt(s.length()-1)) {
            s = s.substring(1, s.length()-1);

            if (s.length() <= 1) {
                return true;
            }
        }

        if (k == 0) {
            return false;
        }

        // Try to remove the first or last character
        return testIt(s.substring(0, s.length() - 1), k - 1) || testIt(s.substring(1, s.length()), k - 1);
    }
}

Since K is max 30 it's likely the string can be invalidated pretty quick and without even examining the middle of the string.

I've tested this with the two provided test cases as well as a 20k characters long string with just "ab" 10k times and k = 30;

All tests are fast and returns the correct results.

Answer 2

This can be solved using Edit distance dynamic programming algorithm. Edit distance DP algorithm is used to find the minimum operations required to convert a source string to destination string. The operations can be either addition or deletion of characters.

The K-palindrome problem can be solved using Edit distance algorithm by checking the minimum operation required to convert the input string to its reverse.

Let editDistance(source,destination) be the function which takes source string and destination string and returns the minimum operations required to convert the source string to destination string.

A string S is K-palindrome if editDistance(S,reverse(S))<=2*K

This is because we can transform the given string S into its reverse by deleting atmost K letters and then inserting the same K letters in different position.

This will be more clear with an example.

Let S=madtam and K=1.

To convert S into reverse of S (i.e matdam) first we have to remove the character 't' at index 3 ( 0 based index) in S.

Now the intermediate string is madam. Then we have to insert the character 't' at index 2 in the intermediate string to get "matdam" which is the reverse of string s.

If you look carefully you will know that the intermediate string "madam" is the palindrome that is obtained by removing k=1 characters.

Answer 3

I found the length of a longest string such that after removing characters >= k, we will be having a palindrome. I have used dynamic programming here. The palindrome I have considered need not be consecutive. Its like abscba has a longest palindromic length of 4.

So now this can be used further, such that whenever k >= (len - len of longest palindrome), it results to true else false.

 public static int longestPalindrome(String s){
        int len = s.length();
        int[][] cal = new int[len][len];
        for(int i=0;i<len;i++){
            cal[i][i] = 1; //considering strings of length = 1
        }
        for(int i=0;i<len-1;i++){
            //considering strings of length = 2
            if (s.charAt(i) == s.charAt(i+1)){
                cal[i][i+1] = 2;
            }else{
                cal[i][i+1] = 0;
            }
        }

        for(int p = len-1; p>=0; p--){
            for(int q=p+2; q<len; q++){
                if (s.charAt(p)==s.charAt(q)){
                    cal[p][q] = 2 + cal[p+1][q-1];
                }else{
                    cal[p][q] = max(cal[p+1][q], cal[p][q-1]);
                }
            }
        }
        return cal[0][len-1];
    }

Answer 4

This is a common interview question, and I'm little surprised that no one has mentioned dynamic programming yet. This problem exhibits optimal substructure (if a string is a k-palindrome, some substrings are also k-palindromes), and overlapping subproblems (the solution requires comparing the same substrings more than once).

This is a special case of the edit distance problem, where we check if a string s can be converted to string p by only deleting characters from either or both strings.

Let the string be s and its reverse rev. Let dp[i][j] be the number of deletions required to convert the first i characters of s to the first j characters of rev. Since deletions have to be done in both strings, if dp[n][n] <= 2 * k, then the string is a k-palindrome.

Base case: When one of the strings is empty, all characters from the other string need to be deleted in order to make them equal.

Time complexity: O(n^2).

Scala code:

def kPalindrome(s: String, k: Int): Boolean = {
    val rev = s.reverse
    val n = s.length
    val dp = Array.ofDim[Int](n + 1, n + 1)

    for (i <- 0 to n; j <- 0 to n) {
      dp(i)(j) = if (i == 0 || j == 0) i + j
      else if (s(i - 1) == rev(j - 1)) dp(i - 1)(j - 1)
      else 1 + math.min(dp(i - 1)(j), dp(i)(j - 1))
    }
    dp(n)(n) <= 2 * k
}

Since we are doing bottom-up DP, an optimization is to return false if at any time i == j && dp[i][j] > 2 * k, since all subsequent i == j must be greater.

Answer 5

Thanks to Andreas, that algo worked like a charm. Here my implementation for anyone who's curious. Slightly different, but fundamentally your same logic:

public static boolean kPalindrome(String s, int k) {
    if (s.length() <= 1) {
        return true;
    }
    char[] c = s.toCharArray();
    if (c[0] != c[c.length - 1]) {
        if (k <= 0) {
            return false;
        } else {
            char[] minusFirst = new char[c.length - 1];
            System.arraycopy(c, 1, minusFirst, 0, c.length - 1);
            char[] minusLast = new char[c.length - 1];
            System.arraycopy(c, 0, minusLast, 0, c.length - 1);
            return kPalindrome(String.valueOf(minusFirst), k - 1)
                   || kPalindrome(String.valueOf(minusLast), k - 1);
        }
    } else {
        char[] minusFirstLast = new char[c.length - 2];
        System.arraycopy(c, 1, minusFirstLast, 0, c.length - 2);
        return kPalindrome(String.valueOf(minusFirstLast), k);
    }
}

Answer 6

This problem can be solved using the famous Longest Common Subsequence(LCS) method. When LCS is applied with the string and the reverse of the given string, then it gives us the longest palindromic subsequence present in the string.

Let the longest palindromic subsequence length of a given string of length string_length be palin_length. Then (string_length - palin_length) gives the number of characters required to be deleted to convert the string to a palindrome. Thus, the given string is k-palindrome if (string_length - palin_length) <= k.

Let me give some examples,

Initial String: madtam (string_length = 6)

Longest Palindromic Subsequence: madam (palin_length = 5)

Number of non-contributing characters: 1 ( string_length - palin_length)

Thus this string is k-palindromic where k>=1. This is because you need to delete atmost k characters ( k or less).

Here is the code snippet:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 10000

int table[MAX+1][MAX+1];
int longest_common_subsequence(char *first_string, char *second_string){
    int first_string_length = strlen(first_string), second_string_length = strlen(second_string);
    int i, j;
    memset( table, 0, sizeof(table));
    for( i=1; i<=first_string_length; i++ ){
        for( j=1; j<=second_string_length; j++){
            if( first_string[i-1] == second_string[j-1] )
                table[i][j] = table[i-1][j-1] + 1;
            else
                table[i][j] = max(table[i-1][j], table[i][j-1]);
        }
    }
    return table[first_string_length][second_string_length];
}

char first_string[MAX], second_string[MAX];

int main(){
    scanf("%s", first_string);
    strcpy(second_string, first_string);
    reverse(second_string, second_string+strlen(second_string));
    int max_palindromic_length = longest_common_subsequence(first_string, second_string);
    int non_contributing_chars = strlen(first_string) - max_palindromic_length;
    if( k >= non_contributing_chars)
        printf("K palindromic!\n");
    else 
        printf("Not K palindromic!\n");
    return 0;
}

Answer 7

I designed a solution purely based on recursion -

public static boolean isKPalindrome(String str, int k) {
            if(str.length() < 2) {
                return true;
            }

            if(str.charAt(0) == str.charAt(str.length()-1)) {
                return isKPalindrome(str.substring(1, str.length()-1), k);
            } else{
                if(k == 0) {
                    return false;
                } else {
                    if(isKPalindrome(str.substring(0, str.length() - 1), k-1)) {                        
                        return true;
                    } else{
                        return isKPalindrome(str.substring(1, str.length()), k-1);
                    }                   
                }
            }
        }

There is no while loop in above implementation as in the accepted answer. Hope it helps somebody looking for it.

Answer 8

   public static boolean failK(String s, int l, int r, int k) {

        if (k < 0)
            return false;

        if (l > r)
            return true;

        if (s.charAt(l) != s.charAt(r)) {
            return failK(s, l + 1, r, k - 1) || failK(s, l, r - 1, k - 1);
        } else {
            return failK(s, l + 1, r - 1, k);
        }
    }