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.