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.