K-Palindrome

Can a given string be transformed into a palindrome by removing at most k characters from it?

0-Palindrome: Two Pointers

Time complexity: O(n).

Space complexity: O(1) auxiliary space.

bool isPalindrome(string s) { {
    int left = 0;
    int right = s.size() - 1;
    while (left <= right) {
        if (s[left] != s[right])
            return false;
        left++;
        right--;
    }
    return true;
}

1-Palindrome: Reduce to 0-Palindrome

Time complexity: O(n).

Space complexity: O(1) auxiliary space.

bool isPalindromeRange(const string& s, int left, int right) {
    while (left <= right) {
        if (s[left] != s[right])
            return false;
        left++;
        right--;
    }
    return true;
}

bool validOnePalindrome(string s) {
    int left = 0;
    int right = s.size() - 1;

    while (left <= right) {
        if (s[left] != s[right])
            return isPalindromeRange(s, left + 1, right) ||
                isPalindromeRange(s, left, right - 1);
        left++;
        right--;
    }

    return true;
}

K-Palindrome

Time complexity: O(n^2).

Space complexity: O(n^2).

bool validKPalindrome(string s) {
}