K-Palindrome

Hard
0/120
profile
Contributed by
12 upvotes
Asked in companies
UberFreshworksSoft Suave

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
1
abba
2
abcca
Sample Output 1 :
True
True
Explanation For Sample Input 1 :
In the first test case, We can make the string “abba” a palindrome by removing ‘b’ at position 2 or 3. 
Hence the answer is True.

In the second test case, We can make the string palindrome by removing either 1 ‘b’ or two ‘c’.
Hence the answer is True.
Sample Input 2 :
2
1
abc
1
abb
Sample Output 2 :
False
True
Hint

Make a copy of string “str”, reverse it, and check how many characters do not match the original string.

Approaches (3)
Recursion Approach

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’
Time Complexity

O( 2 ^ |S| ), where |S| is the length of the String.

 

As we are Checking for every possible palindrome.

Hence the time complexity is O( 2 ^ N ).

Space Complexity

O( 1 ).

 

No extra space is used.

Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
K-Palindrome
Full screen
Console