Check if a string is k–palindrome or not
Write an efficient algorithm to check if a given string is k–palindrome or not. A string is k–palindrome if it becomes a palindrome on removing at most k characters from it.
For example,
Input: ABCDBA, k = 1
Output: k–palindrome
Explanation: The string becomes a palindrome by removing either C or D from it.
Input: ABCDECA, k = 1
Output: Not a k–palindrome
Explanation: The string needs at least 2–removals from it to become a palindrome.
Output: k–palindrome
Explanation: The string becomes a palindrome by removing either C or D from it.
Input: ABCDECA, k = 1
Output: Not a k–palindrome
Explanation: The string needs at least 2–removals from it to become a palindrome.
By carefully analyzing the problem, we can see that it is a variation of the classic Edit Distance Problem, where we need to convert the given string to its reverse by removing at most k characters from it (i.e., only delete operation is allowed).
Please note that we need to perform at most n deletions from the original string and n deletions from the reverse string to make the original string and its reverse equal. Therefore, the expression 2×n <= 2×k is satisfied if the string is k–palindrome.
This approach is demonstrated below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <iostream> #include <string> #include <algorithm> using namespace std; // Function to check if the given string is k–palindrome or not int isKPalindrome(string X, int m, string Y, int n) { // if either string is empty, remove all characters from the other string if (m == 0 || n == 0) { return n + m; } // ignore the last characters of both strings if they are the same // and recur for the remaining characters if (X[m - 1] == Y[n - 1]) { return isKPalindrome(X, m - 1, Y, n - 1); } // if the last character of both strings is different // remove the last character from the first string and recur int x = isKPalindrome(X, m - 1, Y, n); // remove the last character from the second string and recur int y = isKPalindrome(X, m, Y, n - 1); // return one more than the minimum of the above two operations return 1 + min(x, y); } int main() { string s = "CABCBC"; int k = 2; // get reverse of s string rev = s; reverse(rev.begin(), rev.end()); if (isKPalindrome(s, s.length(), rev, s.length()) <= 2*k) { cout << "The string is k–palindrome"; } else { cout << "The string is not a k–palindrome"; } return 0; } |
Output:
The string is k–palindrome
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
class Main { // Function to check if the given string is k–palindrome or not public static int isKPalindrome(String X, int m, String Y, int n) { // if either string is empty, remove all characters from the other string if (m == 0 || n == 0) { return n + m; } // ignore the last characters of both strings if they are the same // and recur for the remaining characters if (X.charAt(m - 1) == Y.charAt(n - 1)) { return isKPalindrome(X, m - 1, Y, n - 1); } // if the last character of both strings is different // remove the last character from the first string and recur int x = isKPalindrome(X, m - 1, Y, n); // remove the last character from the second string and recur int y = isKPalindrome(X, m, Y, n - 1); // return one more than the minimum of the above two operations return 1 + Integer.min(x, y); } public static void main(String[] args) { String s = "CABCBC"; int k = 2; // get reverse of s String rev = new StringBuilder(s).reverse().toString(); if (isKPalindrome(s, s.length(), rev, s.length()) <= 2*k) { System.out.println("The string is k–palindrome"); } else { System.out.println("The string is not a k–palindrome"); } } } |
Output:
The string is k–palindrome
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
# Function to check if the given string is k–palindrome or not def isKPalindrome(X, m, Y, n): # if either string is empty, remove all characters from the other string if m == 0 or n == 0: return n + m # ignore the last characters of both strings if they are the same # and recur for the remaining characters if X[m - 1] == Y[n - 1]: return isKPalindrome(X, m - 1, Y, n - 1) # if the last character of both strings is different # remove the last character from the first string and recur x = isKPalindrome(X, m - 1, Y, n) # remove the last character from the second string and recur y = isKPalindrome(X, m, Y, n - 1) # return one more than the minimum of the above two operations return 1 + min(x, y) if __name__ == '__main__': s = 'CABCBC' k = 2 # get reverse of s rev = s[::-1] if isKPalindrome(s, len(s), rev, len(s)) <= 2*k: print('k-palindrome') else: print('Not a k–palindrome') |
Output:
The string is k–palindrome
The worst-case time complexity of the above solution is O(2n), where n is the length of the input string. The worst case happens when the string contains all different characters. It also requires additional space for the call stack.
The problem has an optimal substructure and exhibits overlapping subproblems. Since both dynamic programming properties are satisfied, we can save subproblem solutions in memory rather than computing them repeatedly. The dynamic programming is demonstrated below in C++, Java, and Python, which runs in O(n2) time:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include <string> #include <algorithm> using namespace std; // Function to check if the given string is k–palindrome or not bool isKPalindrome(string X, int k) { // 'Y' is a reverse of 'X' string Y = X; reverse(Y.begin(), Y.end()); int m = X.length(); int n = m; // lookup table to store solution of already computed subproblems int T[m + 1][n + 1]; // fill the lookup table `T[][]` in a bottom-up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // if either string is empty, remove all characters from the // other string if (i == 0 || j == 0) { T[i][j] = i + j; } // ignore the last characters of both strings if they are the same // and process the remaining characters else if (X[i - 1] == Y[j - 1]) { T[i][j] = T[i - 1][j - 1]; } // if the last character of both strings is different, consider // minimum by removing the last character from 'X' and 'Y' else { T[i][j] = 1 + min(T[i - 1][j], T[i][j - 1]); } } } return T[m][n] <= 2*k; } int main() { string s = "CABCBC"; int k = 2; if (isKPalindrome(s, k)) { cout << "The string is k–palindrome"; } else { cout << "The string is not a k–palindrome"; } return 0; } |
Output:
The string is k–palindrome
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
class Main { // Function to check if the given string is k–palindrome or not public static boolean isKPalindrome(String X, int k) { // 'Y' is a reverse of 'X' String Y = new StringBuilder(X).reverse().toString(); int n = X.length(); // lookup table to store solution of already computed subproblems int[][] T = new int[n + 1][n + 1]; // fill the lookup table `T[][]` in a bottom-up manner for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { // if either string is empty, remove all characters from the // other string if (i == 0 || j == 0) { T[i][j] = i + j; } // ignore the last characters of both strings if they are the same // and process the remaining characters else if (X.charAt(i - 1) == Y.charAt(j - 1)) { T[i][j] = T[i - 1][j - 1]; } // if the last character of both strings is different, consider // minimum by removing the last character from 'X' and 'Y' else { T[i][j] = 1 + Integer.min(T[i - 1][j], T[i][j - 1]); } } } return T[n][n] <= 2*k; } public static void main(String[] args) { String s = "CABCBC"; int k = 2; if (isKPalindrome(s, k)) { System.out.println("The string is k–palindrome"); } else { System.out.println("The string is not a k–palindrome"); } } } |
Output:
The string is k–palindrome
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
# Function to check if the given string is k–palindrome or not def isKPalindrome(X, K): # 'Y' is a reverse of 'X' Y = X[::-1] n = len(X) # lookup table to store solution of already computed subproblems T = [[0 for x in range(n + 1)] for y in range((n + 1))] # fill the lookup table `T[][]` in a bottom-up manner for i in range(n + 1): for j in range(n + 1): # if either string is empty, remove all characters from the # other string if i == 0 or j == 0: T[i][j] = i + j # ignore the last characters of both strings if they are the same # and process the remaining characters elif X[i - 1] == Y[j - 1]: T[i][j] = T[i - 1][j - 1] # if the last character of both strings is different, consider # minimum by removing the last character from 'X' and 'Y' else: T[i][j] = 1 + min(T[i - 1][j], T[i][j - 1]) return T[n][n] <= 2*k if __name__ == '__main__': s = 'CABCBC' k = 2 if isKPalindrome(s, k): print('The string is k–palindrome') else: print('The string is not a k–palindrome') |
Output:
The string is k–palindrome
We can also solve this problem by finding the Longest Palindromic Subsequence (LPS) of a string. To make a string palindrome, the characters that don’t contribute to the LPS should be removed. Therefore, a string is k–palindrome if the difference between the length of LPS and the original string’s length is less than equal to k.
For example, the LPS of string CABCBC is CBCBC, and on removing A from it, the string becomes a palindrome. Following is the C++, Java, and Python implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <iostream> #include <string> #include <algorithm> using namespace std; // Function to check if the given string is k–palindrome or not bool isKPalindrome(string X, int k) { // 'Y' is a reverse of 'X' string Y = X; reverse(Y.begin(), Y.end()); int m = X.length(); int n = m; // lookup table to store solution of already computed subproblems // T[i][j] stores the length of LCS of X[0…i-1] and Y[0…j-1] int T[m + 1][n + 1]; // fill the lookup table in a bottom-up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // special case: first row or first column of the lookup table if (i == 0 || j == 0) { T[i][j] = 0; } // if the current character of 'X' and 'Y' matches else if (X[i - 1] == Y[j - 1]) { T[i][j] = T[i - 1][j - 1] + 1; } // if the current character of 'X' and 'Y' don't match else { T[i][j] = max(T[i - 1][j], T[i][j - 1]); } } } // T[m][n] contains the length of LCS for 'X' and 'Y' // (or longest palindromic subsequence) // For the string to be k–palindrome, the difference between the length of // longest palindromic subsequence and the string should be <= k return (n - T[m][n] <= k); } int main() { string s = "CABCBC"; int k = 2; if (isKPalindrome(s, k)) { cout << "The string is k–palindrome"; } else { cout << "The string is not a k–palindrome"; } return 0; } |
Output:
The string is k–palindrome
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
class Main { // Function to check if the given string is k–palindrome or not public static boolean isKPalindrome(String X, int k) { // 'Y' is a reverse of 'X' String Y = new StringBuilder().append(X).reverse().toString(); int len = Y.length(); // lookup table to store solution of already computed subproblems // T[i][j] stores the length of LCS of X[0…i-1] and Y[0…j-1] int[][] T = new int[len + 1][len + 1]; // fill the lookup table in a bottom-up manner for (int i = 1; i <= len; i++) { for (int j = 1; j <= len; j++) { // if the current character of 'X' and 'Y' matches if (X.charAt(i - 1) == Y.charAt(j - 1)) { T[i][j] = T[i - 1][j - 1] + 1; } // if the current character of 'X' and 'Y' don't match else { T[i][j] = Integer.max(T[i - 1][j], T[i][j - 1]); } } } // T[m][n] contains the length of LCS for 'X' and 'Y' // (or longest palindromic subsequence) // For the string to be k–palindrome, the difference between the length // of longest palindromic subsequence and the string should be <= k return (len - T[len][len] <= k); } public static void main(String[] args) { String s = "CABCBC"; int k = 2; if (isKPalindrome(s, k)) { System.out.println("The string is k–palindrome"); } else { System.out.println("The string is not a k–palindrome"); } } } |
Output:
The string is k–palindrome
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
# Function to check if the given string is k–palindrome or not def isKPalindrome(X, k): # 'Y' is a reverse of 'X' Y = X[::-1] length = len(Y) # lookup table to store solution of already computed subproblems # T[i][j] stores the length of LCS of X[0…i-1] and Y[0…j-1] T = [[0 for x in range(length + 1)] for y in range(length + 1)] # fill the lookup table in a bottom-up manner for i in range(1, length + 1): for j in range(1, length + 1): # if the current character of 'X' and 'Y' matches if X[i - 1] == Y[j - 1]: T[i][j] = T[i - 1][j - 1] + 1 # if the current character of 'X' and 'Y' don't match else: T[i][j] = max(T[i - 1][j], T[i][j - 1]) # T[m][n] contains the length of LCS for 'X' and 'Y' # (or longest palindromic subsequence) # For the string to be k–palindrome, the difference between the length of # longest palindromic subsequence and the string should be <= k return length - T[length][length] <= k if __name__ == '__main__': s = 'CABCBC' k = 2 if isKPalindrome(s, k): print('The string is k–palindrome') else: print('The string is not a k–palindrome') |
Output:
The string is k–palindrome
The time complexity of the above solution is O(n2) and requires O(n2) extra space, where n is the length of the input string.
Author: Aditya Goel
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)