K-Palindrome
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

Question

K-Palindrome

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

Accepted Answer

I had done before the coding test so I solved in same way by splitting whole staring in three parts (start+mid+end).

Accepted Answer

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’

Space Complexity: O(1)Explanation:

O( 1 ).

No extra space is used.

Hence the space complexity is O(1).

Time Complexity: OtherExplanation:

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 ).

Accepted Answer

Top-Down Dynamic Programming

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'.

Space Complexity: OtherExplanation:

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

We are taking a 2D “dp” array to store all the values.

Hence the space complexity is O( |S| ^ 2 ).

Time Complexity: OtherExplanation:

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

We are computing all the possible palindromes and then storing them in the “dp” array, decreasing the time complexity to O( |S| ^ 2 ).

Hence the time complexity is O( |S| ^ 2 ).

Python (3.5)

'''

    Time Complexity : O(|S|^2)

    Space Complexity : O(|S|^2)



    Where, |S| is the length of the string.

'''



from typing import List

from copy import deepcopy





def isPalindromeHelper(s: str, cpy: str, n: int, m: int, dp: List[List[int]]) -> int:



    # Check if the current position is already visited.

    ans = dp[n][m]

    if ans != -1:

        return ans



    # Base Case

    if n == 0:

        return m



    if m == 0:

        return n



    # Check if the current elemetns are equal

    if (s[n - 1] == cpy[m - 1]):

        ans = isPalindromeHelper(s, cpy, n - 1, m - 1, dp)

    else:

        ans = min(isPalindromeHelper(s, cpy, n - 1, m, dp),

                  isPalindromeHelper(s, cpy, n, m - 1, dp)) + 1

    dp[n][m] = ans

    return ans





def isPalindrome(k: int, s: str) -> bool:



    n = len(s)



    dp = [[-1 for i in range(n+1)] for j in range(n+1)]



    # Take a copy of h current string and reverse it

    cpy = deepcopy(s)

    cpy = cpy[::-1]



    # Function call

    ans = isPalindromeHelper(s, cpy, n, n, dp)

    if ans <= 2 * k:

        return True

    else:

        return False

Java (SE 1.8)

/*
    Time Complexity : O(|S|^2)
    Space Complexity : O(|S|^2)

    Where, |S| is the length of the string.
*/

public class Solution {
    public static boolean isPalindrome(int k, String str) {
        int n = str.length();

        // Initialize dp matrix with a large value.
        int[][] dp = new int[n + 1][n + 1];
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= n; j++){
                dp[i][j] = -1;
            }
        }

        // Take a copy of the current string and reverse it.
        String cpy;

        StringBuffer temp = new StringBuffer(str);
        temp.reverse();
        cpy = new String(temp);

        // Function call.
        int ans = isPalindromeHelper(str, cpy, n, n, dp);

        if (ans <= 2 * k) {
            return true;
        }
        else {
            return false;
        }
    }

    public static int isPalindromeHelper(String str, String cpy, int n, int m, int[][] dp) {
        // Check if the current position is already visited.
        if(dp[n][m] != -1){
            return dp[n][m];
        }

        // Base Case.
        if (n == 0) {
            return m;
        }

        if (m == 0) {
            return n;
        }

        int ans = -1;

        // Check if the current elements are equal.
        if (str.charAt(n - 1) == cpy.charAt(m - 1)){
            ans = isPalindromeHelper(str, cpy, n - 1, m - 1, dp);
        }
        else {
            ans = Math.min(isPalindromeHelper(str, cpy, n - 1, m, dp), 
                isPalindromeHelper(str, cpy, n, m - 1, dp)) + 1;
        }

        dp[n][m] = ans;

        return ans;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity : O(|S|^2)
    Space Complexity : O(|S|^2)

    Where, |S| is the length of the string.
*/

int isPalindromeHelper(string &str, string &cpy, int n, int m, vector> &dp) {

	// Check if the current position is already visited.
	int &ans = dp[n][m];
	if (ans != -1) {
		return ans;
	}

	// Base Case.
	if (n == 0) {
		return m;
	}

	if (m == 0) {
		return n;
	}

	// Check if the current elements are equal.
	if (str[n - 1] == cpy[m - 1]) {
		ans = isPalindromeHelper(str, cpy, n - 1, m - 1, dp);
	}

	else {
		ans = min(isPalindromeHelper(str, cpy, n - 1, m, dp), isPalindromeHelper(str, cpy, n, m - 1, dp)) + 1;
	}
	return ans;

}

bool isPalindrome(int k, string &str) {

	int n = str.length();

	// Initialize dp matrix with a large value.
	vector> dp(n + 1, vector(n + 1, -1));

	// Take a copy of the current string and reverse it.
	string cpy = str;
	reverse(cpy.begin(), cpy.end());

	// Function call.
	int ans = isPalindromeHelper(str, cpy, n, n, dp);
	if (ans <= 2 * k) {
		return true;
	}
	else {
		return false;
	}
}

Accepted Answer

Optimised Dynamic Programming

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.
- 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.

Space Complexity: OtherExplanation:

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

We are taking a 1D “dp” array to store all the values.

Hence the space complexity is O( |S| ).

Time Complexity: OtherExplanation:

O( |S| * K ), where |S| is the length of the String and K is the given Number.

Since we are checking at max ‘k’ positions for the current position of the string ‘S'.

Hence the time complexity is O( |S| ^ K ).

Python (3.5)

'''

    Time Complexity : O(|S|*K)

    Space Complexity : O(|S|)



    Where, |S| is the length of the string.

'''





from copy import deepcopy





def isPalindrome(k: int, s: str) -> bool:



    n = len(s)



    # Initialize dp matrix with a large value.

    dp = [100000 for i in range(n+1)]

    prevState = [100000 for i in range(n+1)]



    # Take a copy of the current string and reverse it.

    cpy = deepcopy(s)

    cpy = cpy[::-1]



    # Base case

    for i in range(n):

        prevState[i] = i



    # Iterate through the whole string.

    for i in range(1, n + 1):



        dp[0] = i

        frm = max(1, i - k)

        to = min(n, i + k)



        for j in range(max(1, frm - 1), min(to + 1, n) + 1):

            dp[j] = 100000



        for j in range(frm, to + 1):



            # Check if the current positions are equal.

            if (s[i - 1] == cpy[j - 1]):

                dp[j] = prevState[j - 1]



            else:

                dp[j] = 1 + min(dp[j - 1], prevState[j])

        for j in range(max(1, frm - 1), min(to + 1, n) + 1):

            prevState[j] = dp[j]



    if (dp[n] <= 2 * k):

        return True

    else:

        return False

Java (SE 1.8)

/*
    Time Complexity : O(|S|*K)
    Space Complexity : O(|S|)

    Where, |S| is the length of the string and K is the given number.
*/

public class Solution {
    public static boolean isPalindrome(int k, String str) {
        int n = str.length();

        // Initialize dp matrix with a large value.
        int[] dp = new int[n + 1];
        int[] prevState = new int[n + 1];
        for(int i = 0; i <= n; i++){
            dp[i] = 10000;
        }

        // Take a copy of the current string and reverse it.
        String cpy;

        StringBuffer temp = new StringBuffer(str);
        temp.reverse();
        cpy = new String(temp);

        // Base case.
        for (int i = 0; i <= n; i++) {
            prevState[i] = i;
        }

        // Iterate through the whole string.
        for (int i = 1; i <= n; i++) {
            dp[0] = i;

            int from = Math.max(1, i - k);
            int to = Math.min(n, i + k);

            for (int j = Math.max(1, from - 1); j <= Math.min(to + 1, n); j++) {
                dp[j] = 100000;
            }

            for (int j = from; j <= to; j++) {

                // Check if the current positions are equal.
                if (str.charAt(i - 1) == cpy.charAt(j - 1)) {
                    dp[j] = prevState[j - 1];
                }
                else {
                    dp[j] = 1 + Math.min(dp[j - 1], prevState[j]);
                }
            }

            for (int j = Math.max(1, from - 1); j <= Math.min(to + 1, n); j++) {
                prevState[j] = dp[j];
            }
        }

        if (dp[n] <= 2 * k) {
            return true;
        }
        else {
            return false;
        }
    }
}

C++ (g++ 5.4)

/*
    Time Complexity : O(|S|*K)
    Space Complexity : O(|S|)

    Where, |S| is the length of the string and K is the given number.
*/

#include
bool isPalindrome(int k, string str) {

	int n = str.length();

	// Initialize dp matrix with a large value.
	vector dp(n + 1, 10000);
	vector prevState(n + 1, 10000);

	// Take a copy of the current string and reverse it.
	string cpy = str;
	reverse(cpy.begin(), cpy.end());

	// Base case.
	for (int i = 0; i < n; i++) {
		prevState[i] = i;
	}

	// Iterate through the whole string.
	for (int i = 1; i <= n; i++) {
		dp[0] = i;
		int from = max(1, i - k), to = min(n, i + k);
		for (int j = max(1, from - 1); j <= min(to + 1, n) ; j++) {
			dp[j] = 100000;
		}

		for (int j = from; j <= to; j++) {

			// Check if the current positions are equal.
			if (str[i - 1] == cpy[j - 1]) {
				dp[j] = prevState[j - 1];
			}
			else {
				dp[j] = 1 + min(dp[j - 1], prevState[j]);
			}
		}
		for (int j = max(1, from - 1); j <= min(to + 1, n) ; j++) {
			prevState[j] = dp[j];
		}
	}

	if (dp[n] <= 2 * k) {
		return true;
	}
	else {
		return false;
	}
}

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 :

Input Format :

Output Format :

Note :

Constraints :

Top Uber Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Uber Software Engineer