Find if String is K-Palindrome or not in Java

Given a string S, determine whether it is a K-palindrome. When at most K characters are removed from a K-palindrome string, the string becomes a palindrome.

Here, the task is to remove at most K characters from the given string in order to convert it into its reverse. In basic terms, the issue is an Edit Distance variant. We can change the parameters of the Edit Distance problem so that the input consists of the provided text and its reverse and that the only action permitted is deletion.

Since the provided string is being compared to its reverse, we shall equalize them by removing a maximum of N characters from the first string and N characters from the second. Since 2*N <= 2*K is supposed to be true, then the string is said to be k-palindrome.

Example 1:

Input:

String str = "abccbba"

int k = 1

Output:

Yes, the string is a K-palindrome.

Explanation:

For the given string "abccbba," as the k value is 1, only 1 element has to be removed. Hence, if str[4] = b is removed, then the remaining string is "abccba," which is a palindrome. Hence, the string is a K-Palindrome.

Example 2:

Input:

String str = "abcdeca"

int k = 2

Output:

Yes, the string is a K-palindrome.

Explanation:

For the given string "abcdeca," as the k value is 2, so 2 elements have to be removed. Hence, if str[1] = b and str[4] = e or str[3] = d is removed, then the remaining string is "acdca" or "aceca," which is a palindrome. Hence, the string is a K-Palindrome.

Example 3:

Input:

String str = "badac"

int k = 1

Output:

No, the string is not a K-palindrome.

Explanation:

For the given string "badac", as the k value is 1 so, 1 has an element that has to be removed, but even though it cannot be in a palindromic structure, hence the string is not a K-Palindrome.

Approach: Naïve Recursive Method

Algorithm:

Start processing from the left or right side of both strings and go through each character one by one. There are two possibilities for each set of characters we cross over, so let's start from the right corner.

Step 1: We count the number of remaining strings and ignore the last characters if the last characters of the two strings are the same.

Step 1.1: Thus, we repeat for lengths m-1 and n-1, where m and n are the lengths of str1 and str2, respectively.

Step 2: If the last characters differ, we consider eliminating the last character from the first string and the last character from the second string.

Step 2.1: We then recursively calculate the operations' minimum costs and select the lower of two values.

Step 2.1.1: Remove the final character from str1; repeat steps m-1 and n.

Step 2.1.2: Remove the final character from str2 and repeat steps m and n-1.

Implementation:

FileName: KPalindromeRecursive.java

Output:

Yes, it is a K-Palindrome 

Complexity Analysis:

The Time complexity is O(2n), and It increases exponentially. In the worst scenario, we might have to perform O(2n) operations, and in that scenario, the string would contain all distinct characters. The Space Complexity is O(1).

Approach: Dynamic Programming

In order to determine if a given string is a K-Palindrome or not, this method utilizes the use of a dynamic programming algorithm. It builds a table that stores the subproblem findings and iterates through the strings, comparing characters to determine the minimum number of operations are needed to change one string into another.

Three scenarios are taken into consideration by the method, which applies the appropriate steps in each case: when one string is empty when the strings' final characters match, and when the strings' final characters disagree. In order to determine if the string is a K-Palindrome or not, it finally determines whether the least number of operations needed to turn it into a palindrome is equal to or less than k*2.

Algorithm:

Step 1: Declare a function called KPalindrome that uses dynamic programming to determine the lowest possible number of operations needed to change one string into another.

Step 2: Create a 2D array called a to hold the outcomes of the subproblems.

Step 3: Iterate through strings S1 and S2 iteratively, creating the array according to the following conditions: when one string is empty, when the final characters are the same, and when the final characters are different.

Step 4: Retrieve the lowest possible number of operations needed from the array's bottom-right cell.

Step 5: Declare the Kpalin function that determines the k*2 to compare the minimal number of operations needed to determine whether a string is a K-Palindrome.

Step 6: Reverse the input string and apply the KPalindrome to determine whether the result is a K-Palindrome.

Implementation:

FileName: BottomUpPalindrome.java

Output:

Yes, it is a K-Palindrome 

Complexity Analysis:

The Time complexity is O(n2), where n represents the length of the given string. The Space Complexity is also O(n2), which is used for creating a 2D dp array.