Last Updated: 28 Sep, 2021
K-Palindrome
Hard
Asked in companies
You are given a string ‘str’. You need to find out whether the string is a K-Palindrome or not.
A string is called a K-Palindrome if, after removing at most ‘k’ characters from the string, it can be Transformed into a Palindrome.
For Example :
str = “ababba”, k = 3.
In this example, If we remove one ‘b’ from the 3rd position, then the final string will be “ababa” which is a palindrome.
Hence the answer will be True.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘k’, denoting the maximum number of characters you can remove from the string.
The second line of the test case contains the string “str”.
Output Format :
For each test case, print whether the following string is a K-Palindrome or not.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= |S| <= 1000
1 <= k <= 30
Time limit: 1 sec
Approaches
In this approach, we will make a copy of the original string and reverse it and recursively check if the current characters are equal or not.
The steps are as follows:
- In the “main” function:
- Take a string “cpy” and copy the original string in this string.
- Reverse the “cpy” string.
- Return the function “recursion” and pass the strings “str”, “cpy” and integers ‘k’, ‘m’, ‘n’, where ‘m’ and ‘n’ denote the length of strings “str” and “cpy”, respectively.
- In the “recursion” function:
- Check base conditions:
- If m equals zero return n - 1.
- If n equals zero, return m - 1.
- Check if “str[m-1]” equals “cpy[n-1]”
- Return the function “recursion” and pass the strings “str”, “cpy” and integers ‘k’, ‘m - 1’, ‘n - 1’.
- Else if “str[m - 1]” is not equal to “cpy[n - 1]”:
- Return 1 + minimum of “recursion” passing “str”, “cpy” and integers ‘k’, ‘m - 1’, ‘n’ and “recursion” passing “str”, “cpy” and integers ‘k’, ‘m’, ‘n - 1’
- Check base conditions:
In this approach, we will make a copy of the original string and reverse it and recursively check if the current characters are equal or not, by doing so, we are checking the LCS of these two strings, which will eventually be the longest palindromic substring, as the second string is reverse of the first string.
The steps are as follows:
- In the 'main' function:
- Take a string 'cpy' and copy the original string in this string.
- Reverse the 'cpy' string.
- Take a 2D array ‘dp’ of dimension 'n * n', where ‘dp[i][j]’ means the number of elements that are not equal for the substring ‘str’ of length ‘i’ and substring ‘cpy’ of length ‘j’.
- Return the function 'recursion' and pass the strings 'str', 'cpy' and integers ‘k’, ‘m’, ‘n’, where ‘m’ and ‘n’ denote the length of strings 'str' and 'cpy', respectively.
- In the 'recursion' function:
- Check base conditions i.e., if either of the substrings is of length 0 we will have to make change the other string completely to make it equal to the first string:
- If m equals zero return n.
- If n equals zero return m.
- Check if 'dp[n][m]' is not equal to -1:
- Return dp[n][m].
- Take an integer 'ans'.
- Check if 'str[m-1]' equals 'cpy[n-1]'
- Store the value of the function 'recursion' and pass the strings 'str', 'cpy' and integers ‘k’, ‘m - 1’, ‘n - 1’ in 'ans'.
- Else if 'str[m - 1]' is not equal to 'cpy[n - 1]':
- Store the value 1 + minimum of 'recursion' passing 'str', 'cpy' and integers ‘k’, ‘m - 1’, ‘n’ and 'recursion' passing 'str', 'cpy' and integers ‘k’, ‘m’, ‘n - 1’ in 'ans'.
- Update 'dp[n][m]' = 'ans'.
- Return 'ans'.
- Check base conditions i.e., if either of the substrings is of length 0 we will have to make change the other string completely to make it equal to the first string:
As the value of k is very small, we can take advantage of that fact and reduce its time complexity. The approach is simple. We can only delete a maximum of ‘k’ characters from the current string. This means any position which is more than ‘k’ position away from the current ‘i’ cannot be updated. Hence, we don't have to update the dp array for the size greater than ‘i’ + ‘k’ or less than ‘i’ - ‘k’.
The steps are as follows:
- Take two arrays ‘dp’, ‘prevState’ and initialize it with INT_MAX, where ‘dp[j]’ means the number of elements that are not equal in the string ‘str’ when compared with the substring ‘cpy’ of length ‘j’.
- For the base case, we will update the value of ‘prevState’[i]’ = ‘i’, denoting that if either of the substrings is of length 0 we will have to make ‘i’ changes to the other string to make it equal to the first string.
- Take a string ‘cpy’ and copy the string 'str' into this string and reverse the string.
- Iterate through the loop from 1 to n(say iterator be i):
- Update ‘dp’[0] = ‘i’.
- Take two integers 'from' and 'to' and initialize them with max(1, i - k) and min(i + k, n), respectively.
- Iterate through the loop from 'from' to 'to'(say iterator be j):
- If the character 'str[i - 1]' equals 'cpy[j - 1]':
- Update 'dp[j]' = 'prevState[j - 1]'
- Else Update 'dp[j]' equal to minimum of ('prevState[j]', 'dp[j - 1]') + 1.
- If the character 'str[i - 1]' equals 'cpy[j - 1]':
- Iterate through the loop from 'from' to 'to'(say iterator be j):
- Update ‘prevState’[j] = ‘dp’[j].
- Check if dp[n] is less than 2 * k:
- Return True.
- Else
- Return false.