Facebook Interview Question for Interns


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
32
of 32 vote

The question asks if we can transform the given string S into its reverse deleting at most K letters.
We could modify the traditional Edit-Distance algorithm, considering only deletions, and check if this edit distance is <= K. There is a problem though. S can have length = 20,000 and the Edit-Distance algorithm takes O(N^2). Which is too slow.

(From here on, I'll assume you're familiar with the Edit-Distance algorithm and its DP matrix)

However, we can take advantage of K. We are only interested *if* manage to delete K letters. This means that any position more than K positions away from the main diagonal is useless because its edit distance must exceed those K deletions.

Since we are comparing the string with its reverse, we will do at most K deletions and K insertions (to make them equal). Thus, we need to check if the ModifiedEditDistance is <= 2*K
Here's the code:

int ModifiedEditDistance(const string& a, const string& b, int k) {
	int i, j, n = a.size();
	// for simplicity. we should use only a window of size 2*k+1 or 
	// dp[2][MAX] and alternate rows. only need row i-1
	int dp[MAX][MAX];
	memset(dp, 0x3f, sizeof dp);	// init dp matrix to a value > 1.000.000.000
	for (i = 0 ; i < n; i++)
		dp[i][0] = dp[0][i] = i;

	for (i = 1; i <= n; i++) {
		int from = max(1, i-k), to = min(i+k, n);
		for (j = from; j <= to; j++) {
			if (a[i-1] == b[j-1])			// same character
				dp[i][j] = dp[i-1][j-1];	
			// note that we don't allow letter substitutions
			
			dp[i][j] = min(dp[i][j], 1 + dp[i][j-1]); // delete character j
			dp[i][j] = min(dp[i][j], 1 + dp[i-1][j]); // insert character i
		}
	}
	return dp[n][n];
}
cout << ModifiedEditDistance("abxa", "axba", 1) << endl;  // 2 <= 2*1 - YES
cout << ModifiedEditDistance("abdxa", "axdba", 1) << endl; // 4 > 2*1 - NO
cout << ModifiedEditDistance("abaxbabax", "xababxaba", 2) << endl; // 4 <= 2*2 - YES

We only process 2*K+1 columns per row. So this algorithm works in O(N*K) which is fast enough.

- Miguel Oliveira August 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Killer thinking, +1. Fresh out of college? Just kidding... :-)

- Murali Mohan August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

sort of, but I love these kind of questions/problems :)

- Miguel Oliveira August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

It says by "removing at most k characters", not inserting, which makes it simpler.

- ri August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ce we are comparing the string with its reverse, we will do at most K deletions and K insertions (to make them equal).

why insertions ??

- fword August 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Like I said in the post, we're making the string and its reverse equal. They have both N characters so if we remove K characters, we need to insert K as well to get to size N.

- Miguel Oliveira August 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Clever aproach, but I don't think it works. FIrst, there should be a correspondece between the characters inserted and deleted, which you are not controlling. Second, You can do (1 insertion + 1 deletion)*n times, and you will still be in the main diagonal

- Felipe October 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The correspondence between characters inserted and deleted is done because we're transforming the input string into its reverse. So those operations will lead to a palindrome.

"You can do (1 insertion + 1 deletion)*n times, and you will still be in the main diagonal"
Sure, but the cost will be 2*N. As explained above, the final step is to compare DP[N][N] with 2*K. only then we decide the answer.

- Miguel Oliveira October 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm not sure this works.

Edit distance between 'abax' and 'xaba' is 2.
However, to edit 'abax' to be a palindrome, we need just 1 delete.

- Keith October 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

My bad. Please ignore my earlier comment.

I missed the '<= 2*K ' part.

- Keith October 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Keith, that was explained before. The code answers 2 because it is transforming the string into its reverse. If we need 1 delete in the original string, we need another delete in the reversed string to make them equal. That's why we compare it with 2*K

- Miguel Oliveira October 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@- Miguel Oliveira why not we just run it only till half of the string and save the rest half of the problem
i dont have the complete code but if we are able to match the 1st half and 2nd half
we dont need to do the vice-versa operation

btw nice solution indeed

- kkr.ashish November 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

memset the entire dp array takes O(N^2), so your implementation is actually O(N^2).

- Eric January 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Eric, a N^2 table also wouldn't fit in memory. Refer to the comment in the code

// for simplicity. we should use only a window of size 2*k+1 or
// dp[2][MAX] and alternate rows. only need row i-1

- Miguel Oliveira January 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also, I think the correct outcome for your second case should be 'Yes'(delete x).

- Eric January 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

OOops, ignore the previous comment. It is correct.

- Eric January 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

in edit distance algorithm we are changing only one of the string and Why are you trying to keep the length constant here...insertions are not allowed at all....please clarify

- abhinav May 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It doesnt work for ModifiedEditDistance("abc", "cba", 1).

Here the edit distance would be 2 (which is <=2*1), but wont form a palindrome for k=1 deletions.

- Prashant Shrivastava November 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not a normal edit distance. I do not allow substitutions. If you run the code, you'll see that ModifiedEditDistance("abc", "cba", 1) returns 4 which is larger than 2*K

- Miguel Oliveira November 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice idea but it actually is different from the classical edit distance problem where the first string is transformed into the second. Here we need to perform adjustments on both strings but it works because the cost is the same for delete and add. Otherwise the algorithm should be slightly modified.

- szilard November 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shouldn't the following:

if (a[i-1] == b[j-1])			// same character
				dp[i][j] = dp[i-1][j-1];

be:

if (a[i] == b[j]) // same character
dp[i][j] = dp[i-1][j-1];

- AMGeek December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No. Notice than both i and j are 1-indexed (1..n) due to the DP table. Hence the -1 to get the correct characters.

- Miguel Oliveira December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Does not work for

cout << ModifiedEditDistance("abdxa", "axdba", 1) << endl; // 4 > 2*1 - NO

AND MANY OTHER CASES

- Anonymous March 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Miguel Oliveira
Hi, awesome solution. Instead of having both insertions and deletions, and finally comparing with 2k can you use only replacements of characters not matching with palidrome and assume these as deletions and finally comparing with k instead of 2k. Everything else remaining same as your solution.
Will this work? I just want to know if my line of thinking is correct. Thanks

- vinipani July 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

a little bit simpler idea and implementation -

public void kPalindrome() {
        char [] s= "zayxcbbcxa".toCharArray();
        int k = 2;
        int n = s.length;

        int [][] dp = new int[n+1][n+1];
        dp[0][0] = 0;
        for(int i=1; i<=n; i++) dp[i][0] = dp[0][i] = i;

        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                dp[i][j] = Math.min(dp[i][j-1] + 1, dp[i-1][j] + 1);
                if(s[i-1] == s[n-j]) { // compare 0th with n-1th, 1st with n-2th and so on
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j]);
                }
            }
        }

        // this is tricky, we get the min deletions possible to compare given string and its reverse
        // so dp[n][n] includes, deletions performed on string plus deletions performed on its reverse
        // hence we divide it by 2 to get the number of deletions required to make it a palindrome
       // and trust me dp[n][n] will always be even number ;)
        if(dp[n][n]/2 > k) System.out.println("NO");
        else System.out.println("YES");
    }

- HauntedGhost September 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
8
of 8 vote

I made a recursive algorithm

int kpal(int k, char *str, int i, int j)
{
    if (k < 0)
        return 0;
    else if (i == j)
        return 1;
    // Verify if it's a palindrom
    while (i < j)
    {
        // If it's not, call the function recursively
        if (str[i] != str[j])
        {
            int res = kpal(k-1, str, i+1, j);

            if (!res)
                res = kpal(k-1, str, i, j-1);
            if (!res)
                return 0;
            else
                return 1;
        }
        ++i;--j;
    }
    return 1;
}

- thierrypin September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I made a similar one in java, but I'm not sure if it works... If it doesn't, could you let me know why?

public static boolean isKPalindrome(String str, int num) {
        if ( num < 0 ) return false;
        if (str.length() == 0 || str.length() == 1) {
            return true;
        }
        // start at 2 ends
        char start = str.charAt(0);
        char end = str.charAt(str.length() - 1);

        if ( start == end) {
            return isKPalindrome(str.substring(1, str.length() - 1), num);
        }
	// otherwise do 2 recursive calls 
        return isKPalindrome(str.substring(1, str.length()), num-1) ||
               isKPalindrome(str.substring(0, str.length()-1), num-1);
    }

- chou October 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great. I just would add an unordered map to avoid redundancy in recursion.

- Nima November 19, 2020 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

There are two approaches you may apply. The first one is to reverse the input string and find the LCS of the input string, and it's reversal. This gives you the lenght of the longest palindrom. Now you substract the LCS value from the lenght of the string and you get the k - so just check if it matches.

The second approach just looks for a palindrom. Let's say p[n] is a palindrom with lenght n. Let l will be begining, end e the end of a palindrom. Then we can see that:
1) p[l] == p[h], then we need to check p[l+1] == p[h - 1], i.e abcba, where p[l] == a == p[h]
2a) p[l] != p[h], then we need to check p[l+1],p[h] (we removed p[l])
2b) p[l] != p[h], then we need to check p[l], p[h-1], (we removed p[h])

Now simply use this in your dynamic programming aproach. If you have a problem with that, I am more than glad to help you more.

As I was bored, I typed the code for the second solution:)

bool isKPalindrom(string input, int k)
{
        int answers[input.size() + 1][input.size() + 1];
        int N = input.size();
        for(int i = 0; i <= N; i++)
                for(int j = 0; j <= N; j++)
                        answers[i][j] = 0;


        for(int gap = 1; gap <= N; gap++)
        {
                int l = 1;
                int h = l + gap;
                for(; h <= N; l++, h++)
                {
                        if(input[l-1] == input[h - 1])
                                answers[l][h] = answers[l+1][h-1];
                        else
                                answers[l][h] = 1 + min(answers[l+1][h], answers[l][h-1]);
                }
        }

        return answers[1][N] <= k;
}

- joe kidd August 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This roughly equals to choose 30 from 20000, takes way toooooooo much time!

- Wilbur August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Does not work. LCS of reverse and and string need not be largest palindrome.

- Anonymous August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the LCS method works. Annonymous, can you give a counter-example?

- Miguel Oliveira August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem is that LCS works in O(N^2) so it will be too slow with those limits. There should be another solution taking advantage of k.

- Miguel Oliveira August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Miguel. Try proving that it works.

- Anonymous August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

(A web search should reveal a counter-example, though)

- Anonymous August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

right, it's not necessarily a palindrome. there are ways to make a LCS based approach work though (just found on the web but can't link it here due to this site restrictions).

anyway, i've given an efficient solution to this problem based on edit-distance

- Miguel Oliveira August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think that the LCS approach should work fine. The longest subset in this case would be a base of a palindrom, as we are comparing the same set, just in a different order. Please give a real counter example.

- joe kidd August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@joe_kidd: does this work for {"malayalxam"} with k=1?

- aka August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It looks like. The reversal is maxlayalam, so the longest common subsequence is: malayalam, the lenght difference 1, so it works.

- joe kidd August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@joe for the purpose of this problem, the simple LCS approach works. It would not work if we wanted to find out the palindromic string instead of just its length. Check the page wcipeg . com / Longest_palindromic_subsequence
The longest palindromic subsequence is one of the LCSes but it's not guaranteed that every LCS is palindrome.
"afala" and "alafa" are LCSes of "alfalfa" and its reverse, yet neither is palindromic.

- Miguel Oliveira August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks, the page seems to be very cool not only for this particular case.

- joe kidd August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@joe_kidd : I thought of the same solution as yours before I looked at posted solutions ! I am glad that you also came up that. Well, what do you think is complexity of the algorithm? I think it's O(n). Is that right?

- Parin August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Parin, it's O(N^2) which is too slow

- Miguel Oliveira August 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this question can be solve by following idea.
I define the function like this :
bool isKPalindrom(string s, int start, int end, int k)

The input is string s , its begin position, its end position and k.

If s[start:end] is palindrome then return true
else
if k < 0 return false
else if s[start] == s[end-1] then recursively call isKPalindrome(s,start+1,end-1,k)
else return isKPalindrome(s,start+1,end,k-1 ) || isKPalindrome(s,start,end-1,k-1)

We can also use a array to record the result of whether s[start,end] is palindrome

The time complxity is (n^2)

- gaoxinbo1984 August 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would use recursion to solve this problem:

public static boolean IsKPalindrom(char[] arr, int k) {
	int match = 0;
	if (arr.length <= 1) return true;
	// try to match front and back of the string
	for (match = 0; match < (arr.length / 2); match ++) {
		if (arr[match] != arr[arr.length - match - 1]) {
			break;
		}
	}

	if (match >= (arr.length / 2) {
		// Yeah!
		return true;
 	} else if (k == 0) {
		// not palindrom, and we cannot remove any more characters
		return false;
	} else {
		// remove 1 char and call recursively
		return isKPalindrom(arr.subarray(match + 1, arr.length - match - 1), k - 1) ||
			  isKPalindrom(arr.subarray(match, arr.length - match - 2), k - 1);
	}
}

- lngbrc August 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Given that array.subArray() is O(1). This also runs in O(n) doesn't it?

- Anonymous September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

subArray does not run in O(1) but O(N).
anyway this recursive approach runs in exponential time

- Miguel Oliveira September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@joe_kidd : I thought of the same solution as yours before I looked at posted solutions ! I am glad that you also came up that. Well, what do you think is complexity of the algorithm? I think it's O(n). Is that right?

- Parin August 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@joe_kidd : I thought of the same solution as yours before I looked at posted solutions ! I am glad that you also came up that. Well, what do you think is complexity of the algorithm? I think it's O(n). Is that right?

- Parin August 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

This is a recursive approach, and works for all possible cases.

This is a back tract approach. Maximum matches can be n (n is the size of input array) and minimum matches can be n-k.

public class KPalendrome {
	
	static char[] array = {'a','b','a','c','a','b','a','x','l','o','p','a','m','b'};
	static int k = 3; 

	public static void main(String[] args) {
		
		final int MAX = array.length;
		final int MIN = array.length - k;
		System.out.println(new KPalendrome().kPalendrome(0, array.length-1, 0, MAX, MIN));		
	}
	
	public boolean kPalendrome(int start, int end, int matches, int MAX, int MIN)
	{	
		if (start == end)
		{
			matches++;
		}
		
		if(matches >= MIN && matches <=MAX)
		{
			return true;
		}
		
		if(start > end)
		{
			return false;
		}				
				
		if(array[start] == array[end])
		{
			return kPalendrome(start+1, end-1, matches+2, MAX, MIN);
		}
		else
		{
			return kPalendrome(start, end-1, matches, MAX, MIN) || kPalendrome(start+1, end, matches, MAX, MIN);
		}
	}
	
}

- obaid salikeen August 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code:

def isPalindrome(String):
stringSize = len(String)
start = 0
end = stringSize - 1
while start < end and String[start] == String[end]:
start += 1
end -= 1
if start < end:
return False
else:
return True

def isKPalindrome(String, k):
if k > 0:
for i in range(len(String)):
subString = String[:i] + String[i+1:]
if isKPalindrome(subString, k-1) == True:
return True
return False
elif k == 0:
return isPalindrome(String)
else:
print 'Error number k'
return False


Testing Set:
print isPalindrome('1')
print isPalindrome('11')
print isPalindrome('11111')
print isPalindrome('11211')
print isPalindrome('13231')
print isPalindrome('1221')
print isPalindrome('133121331')

print isPalindrome('11221')
print isPalindrome('13211')
print isPalindrome('23')
print isPalindrome('123')

print isKPalindrome('abxa', 1)
print isKPalindrome('abxa', 2)
print isKPalindrome('abdxa', 2)
print isKPalindrome('abdxa', 1)

- yinzhengliang August 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How could I indent?

- yinzhengliang August 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

inpt = raw_input('Enter a string and an integer: ')
inpt = inpt.split(' ')
string = inpt[0]
k = int(inpt[1])
position = 0

def kPalindrome(string,pos,k):
	if string == string[::-1]:
		print 'True: ', string
	elif k > 0:
		if len(string) - pos > k:
			for i in range(pos,len(string)):
				kPalindrome(string[:i]+string[i+1:],pos,k-1)
				pos += 1
			
kPalindrome(string,position,k)

- Daniel Lewis September 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Correction to previous python solution:

inpt = raw_input('Enter a string and an integer: ')
inpt = inpt.split(' ')
string = inpt[0]
k = int(inpt[1])
position = 0

def kPalindrome(string,pos,k):
	if string == string[::-1]:
		print 'True: ', string
	elif k > 0:
		if len(string) - pos > k:
			for i in range(pos,len(string)):
				kPalindrome(string[:i]+string[i+1:],pos,k-1)
				pos += 1
		else:
			k = len(string)
			for i in range(pos,len(string)):
				kPalindrome(string[:i]+string[i+1:],pos,k-1)
				pos += 1
			
kPalindrome(string,position,k)

- djlewis September 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
int main()
{
int k,i=0,j,flag=1,count=0;
char a[20];
printf("ENTER THE VALUE OF K");
scanf("%d",&k);
printf("ENTER THE STRING");
scanf("%s",a);
j=strlen(a);
j=j-1;
while(i<j)
{
if(a[i]!=a[j])
{
if(a[i+1]==a[j])
{
count++;
}
else if(a[i]==a[j-1])
{
count++;
}
else
{
flag=0;
break;
}
}
if(count>k)
{
flag=0;
break;
}
i++;
j--;

}
if(flag==0)
printf("NO");
else
printf("YES");
getch();
}

- Anonymous September 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

map <pair<int,int>, int> F; 
 
int min(int a, int b, int c) 
{ 
    return min(min(a,b),c); 
} 
 
int f(const string &s, int i, int j, int k) 
{ 
    if (k < 0) 
        return MAX; 
    else if (i >= j) 
        return 0; 
 
    if (F.find(mp(i,j)) != F.end()) 
    { 
        return F[mp(i,j)]; 
    } 
 
    if (s[i] == s[j])  
    { 
        int tmp_result = min(f(s, i+1, j-1, k), f(s, i+1, j, k-1) + 1, f(s, i, j-1, k-1) + 1); 
        F[mp(i,j)] = tmp_result; 
        return tmp_result; 
    } else { 
        int tmp_result = min(f(s, i+1, j, k-1), f(s, i, j-1, k-1)) + 1; 
        F[mp(i,j)] = tmp_result; 
        return tmp_result; 
    } 
}

I think this piece of code should work and pretty much self descriptive. I'm still questioning what would be the complexity it's definitely O(n^2), but I think there is better estimation and should be lower, many branches will be cut by checking if k < 0 condition.

Does anybody have an idea?

- Roman September 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

boolean isKPalindromeRec(char[] arr, int k, int left, int right){
		
		if( left >= right ){
			return k >= 0;
		}
		
		if( arr[left] == arr[right] ){
			return isKPalindromeRec(arr, k, left+1, right-1);
		}
		
		return isKPalindromeRec(arr, k-1, left+1, right) || isKPalindromeRec(arr, k-1, left, right-1);		
	}

- maks September 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@maks - this does not work

- init.d November 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about this one?

def palin_k(str, k):
if k == 0 or str == str[::-1]:
return str == str[::-1]
l_index = 0
r_index = len(str) - 1
while str[l_index] == str[r_index]:
l_index = l_index + 1
r_index = r_index - 1
return palin_k(str[l_index:r_index], k-1) or palin_k(str[l_index+1:r_index+1], k-1)

- TJ October 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you can do something like that :

public static boolean palindromeK(String word, int k, int i, int j, char c) {
		if (k < 0) // we have already removed more than k characters
			return false;
		if (i == j)
			return c == 0;
		if (c == 0) { // we are removing characters from the beginning
			if (palindromeK(word, k, i+1, j, word.charAt(i))) // we use the first character
				return true;
			return palindromeK(word, k-1, i+1, j, (char) 0); // or not
		} else {
			if (word.charAt(j) == c)
				return palindromeK(word, k, i, j-1, (char) 0);
			else
				return palindromeK(word, k-1, i, j-1, c);
		}
	}

and call the function with :
palindromeK(word, k, 0, word.length()-1, (char) 0);

Basically you successively look at the beginning / the end of your word, and you remove a character when you know you can't using it to make a palindrome.
The cost if O(n²)

- guismay October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def is_k_palindrome(word, K):
    # Check upfront if it's a palindrome.
    # This will catch the one-character case.
    if word == word[::-1]:
        return True

    # Not a palindrome and we're out of removal options, so there's no hope.
    if K == 0:
        return False

    if word[0] == word[-1]:
        return is_k_palindrome(word[1:-1], K)

    return (is_k_palindrome(word[1:], K - 1) or
            is_k_palindrome(word[:-1], K - 1))

- twigfiggly October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is in javascript, I measure the distance of the palindrome of the string and divide it by 2, since it each extra character will appear twice

var s1 = "aabbbxxxaa";
console.log(distanceOfPalindrome(s1));

function distanceOfPalindrome(s1)
{
	var rev="";
	for (var i = s1.length - 1; i >= 0; i--) {
		rev += s1[i];
	};
	return distance(s1,rev) / 2;
}

function distance(s1,rev)
{
	if(s1.length == 0 || rev.length==0)
	{
		return Math.abs(s1.length-rev.length);
	}

	if(s1[0] == rev[0])
	{
		return 
        distance(s1.substring(1, s1.length), rev.substring(1, rev.length));
	}
	else
	{
		var d1 = distance(s1.substring(1, s1.length), rev);
		var d2 = distance(s1, rev.substring(1, rev.length));
		
		return Math.min(d1,d2) + 1;
	}
}

- pablito October 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@miguel - great solution! i used the dp / edit distance approach like you suggested and i think it works.. not sure if i did it exactly like you said... but same general idea..

private static boolean isKPalindrome(String s, int k) {
		boolean result = false;
		String r = new StringBuilder(s).reverse().toString();
		
		char[] sc = s.toCharArray();
		char[] rc = r.toCharArray();
		
		int[][] t = new int[s.length()/2 + 1][s.length()/2 + 1];
		
		int i = 0;
		int j = 0;
		
		for (;i<t.length;i++) {
			t[i][0] = i;			
		}
		for (;j<t[0].length;j++) {
			t[0][j] = j;			
		}
		for (i = 1; i < t.length;i++) {
			for (j = 1; j < t.length;j++) {
				int c =0;
				if(sc[i] == rc[j]) {
					c = 0;
				} else {
					c = 2;
				}
				t[i][j] = Math.min(Math.min(t[i-1][j] +1 , t[i][j-1] + 1), c + t[i-1][j-1]);
				if(i == t.length-1 || j == t.length-1) {
					result = t[i][j] <= k ? true : false;
					break;
				}
			}
		}
		return result;
	}

- init.d November 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

never mind. i found a bug in my above code. it does not work for this input isKPalindrome("sbandanarb", 5)

- init.d November 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// C Version - Recursive approach.

bool isKPalindrom(char * str, int len, int k)
{
	while (len >=1 && str[0] == str[len-1])
	{
		str++; len-=2;
	}

	if (len <= 1) return true;

	if (k > 0)
		return isKPalindrom(str + 1, len-1, k-1) || isKPalindrom(str, len-1, k-1);

	return false;
}

- sachin.sde November 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hmm that's pure backtracking.
Dynamic programming implies that you're saving subproblems results somewhere (like a table) and reusing them later.

- Miguel Oliveira November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agreed! :) Modified comments accordingly.

- sachin.sde November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String isKPalindrome(String input, int k) {

		if (k >= (input.length() - 1)) {
			return "YES";
		} else if (input.charAt(0) == input.charAt(input.length() - 1)) {
			input = input.substring(1, input.length() - 1);
			return isKPalindrome(input, k);
		} else if (k > 0) {
			k--;
			String input1 = input.substring(0, input.length() - 1);
			String input2 = input.substring(1, input.length());

			String res1 = isKPalindrome(input1, k);
			String res2 = isKPalindrome(input2, k);
			
			if ("YES".equals(res1) || "YES".equals(res2)) {
				return "YES";
			} else {
				return "NO";
			}

		}

		return "NO";
	}

- besson November 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

LCS should work, the worst case is O(N^2) when there is no match.
But we would be able to return early when this is match with K.

bool isKPalindrom(string input, int k)
	{
		string reverse = reverseStr(input);
		int n = input.length();
		vector<int> v(n+1, 0);
		int max = n-k;
		for(int i=0; i<n; i++){
			vector<int> nv(n+1, 0);
			for(int j=0; j<n; j++)
			{
				int c = input[j] == reverse[i] ? 1 + v[j] : 0;
				nv[j+1] = maxNum(c, v[j+1], nv[j]);
				if (nv[j+1] == max)
					return true;
			}
			v = nv;
		}
		return false;
	}

	string reverseStr(string input)
	{
		int n = input.length();
		for(int i=0; i<= n/2; i++)
		{
			int t = input[i];
			input[i] = input[n-1-i];
			input[n-1-i] = t;
		}
		return input;
	}

	int maxNum(int n1, int n2, int n3)
	{
		n1 = n1<n2? n2: n1;
		n1 = n1 < n3? n3: n1;
		return n1;
	}

- BIN December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There is another DP solution:
Firstly I will present a simple quadratic solution
dp[l][r] - state where we hold minimum number of removes in order to transform the segnment s[l]...s[r] into palindrome. Transitions will be as follows: if(s[l] == s[r]) dp[l][r] = min(dp[l][r], dp[l + 1][r - 1]);
else dp[[l][r] = min(dp[l][r], min(dp[l + 1][r], dp[l][r - 1]) + 1);
But the problem is in that it works too slowly, therefore we can convert our solution by the following way:
dp[l][k] - will hold the rightmost position in S where we can reach removing exactly k characters and starting from l;
if(S[dp[l + 1][k]] == s[l]) dp[l][k] = max(dp[l][k], dp[l + 1][k] + 1);
else dp[l][k] = max(dp[l][k], dp[l + 1][k - 1] + 1);
The implementation demands to go through from right to left;
At the end it is enough just to look at states dp[0][i], where 0<=i <= k;
if(dp[0][i] == s.length()) then "yes"
else "no";

- Askhat January 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in java-

Take an array R of size 26.

Loop through each character of the string and increment the index of R for that character.

If a string is palindrome then the count of each character in R %2 will give 0 and if string length is odd then except one character rest of character's count %2 will be 0.

Now, if you want to calculate k-palindrom add the k to the comparison as shown below.

public static boolean isPalindrome(String s, int k) {

        int[] R = new int[26];

        for(int i=0; i < s.length(); i++)
            R[s.charAt(i) - 'a']++;

        int n = 0;
        for(int i=0; i < R.length; i++)
            if((R[i] % 2) != 0)
                n++;

        return n <= k+1;//Here +1 is for string having odd length

    }

- kapilraju January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool is_palindrome(char* text, const uint& text_size, const int& k)
{
    if (text_size == 0 || k < 0)
        return false;
    if (text_size == 1 || (text_size == 2 && (text[0] == text[1] || k > 0)))
        return true;

    if (text[0] == text[text_size - 1])
        return is_palindrome(text + 1, text_size - 2, k);
    if (text[0] == text[text_size - 2])
        return is_palindrome(text + 1, text_size - 3, k - 1);
    if (text[1] == text[text_size - 1])
        return is_palindrome(text + 2, text_size - 3, k - 1);

    return is_palindrome(text + 2, text_size - 2, k - 2);
}

- donkey code January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Quick explanation:

Start at the borders and collapse, if borders are equal, then continue with the rest of the string, otherwise, check if you can take one border out so that you can still form a valid palindrome with the other border, if not, take out both borders.

O(n) since you only traverse the string once.

- donkey code January 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

find the longest palindromic subsequence. get its difference with length of string , say diff.
if diff <= k , then its a k-pali string.

- Amit January 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Below are my solutions in C++. The first one is a recursive function which gives a good idea of how to tackle the problem. This solution has a huge complexity (something like O(L * 2^K) though I cannot prove an exact formula - L is the length of the string).

The second one is a solution which uses a matrix of size 2*L*K^2 and which fills it step by step (a change of indices is used to avoid building a L * L * K matrix). This solution has O(L*K^2) complexity which is quite acceptable with the given parameters.

#include <iostream>
#include <string>

using namespace std;

int isPalindromeRec(string s, int K) {
    if (s.length() <= 1)
        return 1;
    if (s[0] == s[s.length() - 1]) {
        return isPalindromeRec(s.substr(1, s.length() - 2), K);
    } else {
        if (K == 0)
            return 0;
        return isPalindromeRec(s.substr(1, s.length() - 1), K - 1)
                ||
               isPalindromeRec(s.substr(0, s.length() - 1), K - 1);
    }
}

#define _u(i, l)   (2 * (i) + (l) - L + K)
#define _i(u, l)   (((u) - (l) + L - K) / 2)
int isPalindrome(string s, int K) {
    int L = s.length();
    int P[L + 1][K + 1][2 * K + 1];
    int i, u, l, k;
    for (i = 0; i < L; ++i) {
        P[0][_u(i, 0)][0] = 1;
        P[1][0][_u(i, 1)] = 1;
    }
    for (l = 2; l <= L; ++l) {
        for (k = 0; k <= K; ++k) {
            for (i = max(0, _i(_u(0, l), l)); i < L - l + 1; ++i) {
                u = _u(i, l);
                if (u > 2 * K)
                    break;
                if (s[i] == s[i + l - 1]) {
                    P[l][k][u] = P[l - 2][k][_u(i + 1, l - 2)];
                } else {
                    if (k == 0) {
                        P[l][k][u] = 0;
                    } else {
                        P[l][k][u] = P[l - 1][k - 1][_u(i + 1, l - 1)]
                                        ||
                                     P[l - 1][k - 1][_u(i, l - 1)];
                    }
                }
            }
        }
    }
    return P[L][K][_u(0, L)];
}

int main(int argc, char **argv) {
    string s1 = "abbz",         // 2-palindrome
           s2 = "aubdggdxa",    // 3-palindrome
           s3 = "abcdefghijk";  // 10-palindrome
    // 0
    cout << isPalindromeRec(s1, 1) << endl;
    cout << isPalindrome(s1, 1) << endl;
    // 1
    cout << isPalindromeRec(s1, 2) << endl;
    cout << isPalindrome(s1, 2) << endl;
    // 0
    cout << isPalindromeRec(s2, 2) << endl;
    cout << isPalindrome(s2, 2) << endl;
    // 1
    cout << isPalindromeRec(s2, 3) << endl;
    cout << isPalindrome(s2, 3) << endl;
    // 0
    cout << isPalindromeRec(s3, 9) << endl;
    cout << isPalindrome(s3, 9) << endl;
    // 1
    cout << isPalindromeRec(s3, 10) << endl;
    cout << isPalindrome(s3, 10) << endl;
}

- Thomas February 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Line 6 is

P[1][0][_u(i, 1)] = 1;

actually.

- Thomas February 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Couldn't help adding a Scala solution. I believe that this runs in O(n/2 + 2*K)

def kPal(l:List[Char], k:Int):Boolean = {
  l match {
    case h::t::Nil => (h == t && k == 0) || (h != t && k == 1)
    case h::Nil    => k == 0
    case h::n::t   => if (h == t.last) kPal(n :: t.reverse.tail.reverse, k)
                      else kPal(n::t, k - 1) || kPal(h :: n :: t.reverse.tail.reverse, k - 1)
    case List()    => k == 0
  }
}

To prep:

def findKpal(s:String, k: Int) = kPal(s.toList, k)

Runs:

scala> findKpal("abxa",1)
res0: Boolean = true

scala> findKpal("abxa",0)
res1: Boolean = false

scala> findKpal("aba",0)
res2: Boolean = true

- Steve Schleimer May 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Couldn't help adding a Scala solution. I believe that this runs in O(n/2 + 2*K)

def kPal(l:List[Char], k:Int):Boolean = {
  l match {
    case h::t::Nil => (h == t && k == 0) || (h != t && k == 1)
    case h::Nil    => k == 0
    case h::n::t   => if (h == t.last) kPal(n :: t.reverse.tail.reverse, k)
                      else kPal(n::t, k - 1) || kPal(h :: n :: t.reverse.tail.reverse, k - 1)
    case List()    => k == 0
  }
}

To prep:

def findKpal(s:String, k: Int) = kPal(s.toList, k)

Runs:

scala> findKpal("abxa",1)
res0: Boolean = true

scala> findKpal("abxa",0)
res1: Boolean = false

scala> findKpal("aba",0)
res2: Boolean = true

scala> findKpal("axxbababa",2)
res3: Boolean = true

- Steve Schleimer May 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a naive solution in python, the time complexity is not acceptable for the input bounds but it may help you if you are stuck before moving to a faster solution posted above.

{{def isPalindrome(str):
if (str == str[::-1]):
return True
else:
return False

def isKPalindrome(str, k):
if (len(str) <= 1 or k < 0):
return False
elif(isPalindrome(str)):
return True

for i in range(len(str)):
smallerStr = str[:i] + str[i+1:]
if (isKPalindrome(smallerStr, k-1)):
return True
return False

print isKPalindrome("aaybbaxa", 2)
print isKPalindrome("aaybbaxa", 1)}}

- Luke Walsh May 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a naive solution in python, the time complexity is not acceptable for the input bounds but it may help you if you are stuck before moving to a faster solution posted above.

def isPalindrome(str): 
    if (str == str[::-1]): 
        return True 
    else: 
        return False 

def isKPalindrome(str, k): 
    if (len(str) <= 1 or k < 0): 
        return False 
    elif(isPalindrome(str)): 
        return True 

    for i in range(len(str)): 
        smallerStr = str[:i] + str[i+1:] 
        if (isKPalindrome(smallerStr, k-1)): 
            return True 
    return False 

print isKPalindrome("aaybbaxa", 2) 
print isKPalindrome("aaybbaxa", 1)

- Luke.walsh23 May 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a recursive solution in Objective-C, with a complexity of `O(n)`, where `n` is the number of characters in the string.

// KPalindrome.h

#import <Foundation/Foundation.h>

/**
 Determines whether string is a k-palindrome (case-sensitive, whitespace counts).
 Raises if string is nil. Returns YES for empty or one-character strings.
 Complexity: O(n), where n is the number of characters in string.
 */
extern BOOL ccp_isKPalindrome(NSString *string, NSUInteger k);

// KPalindrome.m

#import "KPalindrome.h"

extern BOOL ccp_isKPalindrome(NSString *string, NSUInteger k) {
    if (string == nil) {
        // Raise if string is nil.
        [NSException raise:NSInvalidArgumentException
                    format:@"string cannot be nil"];
    } else if ([string length] <= 1) {
        // Return YES if string is empty "" or one character "a",
        // as it most certainly is the same backwards and forwards.
        return YES;
    }

    // Split the string into two halves, then reverse the second half.
    // If the string is an odd number of characters, the second half will be longer.
    NSUInteger middle = [string length]/2;
    NSString *front = [string substringToIndex:middle];
    NSString *back = [string substringFromIndex:middle];

    for (NSUInteger i = 0; i < [front length]; ++i) {
        // Iterate over each character of the front and back strings.
        NSRange frontRange = NSMakeRange(i, 1);
        NSRange backRange = NSMakeRange([back length] - 1 - i, 1);
        NSString *frontCharacter = [front substringWithRange:frontRange];
        NSString *backCharacter = [back substringWithRange:backRange];

        if ([frontCharacter compare:backCharacter] != NSOrderedSame) {
            if (k == 0) {
                // If they're not the same, and we can no longer remove any
                // characters, then game over: these are not palindromes.
                return NO;
            } else {
                // If we *can* remove a character, do so and try again.
                NSMutableString *newBack = [back mutableCopy];
                [newBack deleteCharactersInRange:backRange];
                return ccp_isKPalindrome([NSString stringWithFormat:@"%@%@", front, newBack],
                                         k - 1);
            }
        }
    }

    // If we've iterated over each character and haven't exceeded our allotment
    // of removable characters, we have two k-palindromes.
    return YES;
}

// KPalindromeSpec.m

#import <Kiwi/Kiwi.h>
#import "KPalindrome.h"

SPEC_BEGIN(KPalindromeSpec)

describe(@"mdc_isKPalindrome", ^{
    context(@"when the string is nil", ^{
        it(@"raises", ^{
            [[theBlock(^{ ccp_isKPalindrome(nil, 0); }) should] raise];
        });
    });

    context(@"when the string is empty", ^{
        it(@"returns YES", ^{
            [[theValue(ccp_isKPalindrome(@"", 0)) should] beYes];
        });
    });

    context(@"when the string is a palindrome", ^{
        it(@"returns YES", ^{
            [[theValue(ccp_isKPalindrome(@"abccba", 0)) should] beYes];
        });
    });

    context(@"when the string is a k-palindrome", ^{
        it(@"returns YES", ^{
            [[theValue(ccp_isKPalindrome(@"abxa", 1)) should] beYes];
            [[theValue(ccp_isKPalindrome(@"abxaxx", 3)) should] beYes];
        });
    });

    context(@"when the string is not a k-palindrome", ^{
        it(@"returns NO", ^{
            [[theValue(ccp_isKPalindrome(@"abdxa", 1)) should] beNo];
            [[theValue(ccp_isKPalindrome(@"abxaxx", 2)) should] beNo];
        });

        context(@"and string and k are huge", ^{
            __block NSString *string = nil;
            __block NSUInteger k = 0;
            beforeEach(^{
                string = [NSString stringWithContentsOfFile:@"/var/log/system.log"
                                                   encoding:NSUTF8StringEncoding
                                                      error:nil];
                k = 30;
            });

            it(@"returns NO", ^{
                [[theValue(ccp_isKPalindrome(string, k)) should] beNo];
            });
        });
    });
});

SPEC_END

- mdc May 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a solution in JavaScript:

function isPalindrome(s, k) {
  
  function match(i,j,e) {
    if (e>k) return false;
    while (i<=j && s[i] === s[j]) {i++; j--;};
    if (i>j) return true;
    else {
      return match(i,j-1,e+1) || match(i+1,j,e+1);
    }
  }
  return match(0, s.length-1,0);
}

A working version at - codepen.io/yusufnb/pen/veDBx?editors=001

- y1426i June 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinDeletionsToMakePalindrome {
	
	static boolean isKPalindrome(String s, int K){
		if(s == null){
			return false;
		}
		
		int m = minDeletionsToMakePalindrome(s);
		if(m <= K){
			return true;
		} else {
			return false;
		}
	}
	
	static int minDeletionsToMakePalindrome(String s){
		char[] sChar = s.toCharArray();
		int n = sChar.length;
		
		char sInvChar[] = new char[n];
		for(int i = 0; i < n; i++){
			sInvChar[i] = sChar[n-1-i];
		}
		String sInv = new String(sInvChar);
		
		int m = computeEditDistance(s, sInv);
		return (int) Math.ceil((float)m/2.0);
	}
	
		static int computeEditDistance(String s1, String s2){
		    int n1 = s1.length();
		    int n2 = s2.length();
		    char[] s1_c = s1.toCharArray();
		    char[] s2_c = s2.toCharArray();
		    
		    int[][] d = new int[n1+1][n2+1];
		    for(int i1 = 0; i1 <= n1; i1++){
		    	d[i1][0] = i1;
		    }
		    for(int i2 = 0; i2 <= n2; i2++){
		    	d[0][i2] = i2;
		    }
		    
		    for(int i1 = 1; i1 <= n1; i1++){
		    	for(int i2 = 1; i2 <= n2; i2++){
		    		int d10 = d[i1-1][i2]+1;
		    		int d01 = d[i1][i2-1]+1;
		    		int dmin = Math.min(d10, d01);
		    		if(s1_c[i1-1] == s2_c[i2-1]){
		    			int d00 = d[i1-1][i2-1];
		    			dmin = Math.min(dmin, d00);
		    		}
		    		d[i1][i2] = dmin;
		    	}
		    }
		    
		    return d[n1][n2];
	   }
	   
	   public static void main(String[] args){
		   
		   System.out.println("test edit distance calc:\t" + computeEditDistance("bb","cbb"));
		  
		   
		   String[] testcases = {"a" , "aa", "abxa" , "abdxa" , "dbaacbd" , "bdaacbd"};
		   int[] results = {0 , 0 , 1 , 2 , 1 , 3 };
		   for(int i = 0; i < testcases.length; i++){
			   String s = testcases[i];
			   int n = minDeletionsToMakePalindrome(s);
			   System.out.println(s + "\t" + n + "\t" + results[i]);
		   }
	   }

}

- just_do_it July 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure if this will work...you guys critique. Written in Python3:

def kPalendromeCheck(s, k):   #given string s and int k
	if (k < 0):
		return False
	if (s == s[::-1]):
		return True
	for i in range(0, len(s) - 1):
		kPalendromeCheck(s[:i] + s[i+1:], k-1)
	return False

- soultanis September 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n)

private static void mySolution(String palindrome){
        char word[] = palindrome.toCharArray();
        
        boolean flag = false;
        for (int i = 0, j = word.length - 1; j > word.length/2; i++) {
            
            if(word[i] == word[j]){
                j--;
            }else{
                if(flag){
                    System.out.println("NO");
                    return;
                }
                if(word[i] == word[j-1]){
                    j--;
                }
                flag = true;
            }
        }
        System.out.println("YES");
    }

- Magemello February 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is actually fairly easy with recursion:

#include <iostream>
#include <string>
using namespace std;

bool k_pal_helper(const string& input, unsigned k, unsigned l, unsigned r)
{
  cout << input << ": k=" << k << " l=" << l << " r=" << r << endl;
  
  if (r <= l)
    return true;
  
  if (input[l] == input[r])
    return k_pal_helper(input, k, l+1, r-1);
  
  if (k == 0)
    return false;

  // k > 0, first try delete from left
  bool result = k_pal_helper(input, k-1, l+1, r);
  if (result)
    return true;
  
  // then try delete from right
  result = k_pal_helper(input, k-1, l, r-1);
  if (result)
    return true;
  
  return false;
}

bool k_pal(const string& input, unsigned k)
{
  return k_pal_helper(input, k, 0, input.size()-1);
}

int main()
{
  cout << (k_pal("abxxxca", 1) ? "YES" : "NO") << endl;
  cout << (k_pal("abxxxca", 2) ? "YES" : "NO") << endl;
  cout << (k_pal("abxxca", 1) ? "YES" : "NO") << endl;
  cout << (k_pal("abxxca", 2) ? "YES" : "NO") << endl;
  cout << (k_pal("axxbababa", 2) ? "YES" : "NO") << endl;
  return 0;
}

- finalpatch July 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
using namespace std;

bool k_pal_helper(const string& input, unsigned k, unsigned l, unsigned r)
{
  cout << input << ": k=" << k << " l=" << l << " r=" << r << endl;
  
  if (r <= l)
    return true;
  
  if (input[l] == input[r])
    return k_pal_helper(input, k, l+1, r-1);
  
  if (k == 0)
    return false;

  // k > 0, first try delete from left
  bool result = k_pal_helper(input, k-1, l+1, r);
  if (result)
    return true;
  
  // then try delete from right
  result = k_pal_helper(input, k-1, l, r-1);
  if (result)
    return true;
  
  return false;
}

bool k_pal(const string& input, unsigned k)
{
  return k_pal_helper(input, k, 0, input.size()-1);
}

int main()
{
  cout << (k_pal("abxxxca", 1) ? "YES" : "NO") << endl;
  cout << (k_pal("abxxxca", 2) ? "YES" : "NO") << endl;
  cout << (k_pal("abxxca", 1) ? "YES" : "NO") << endl;
  cout << (k_pal("abxxca", 2) ? "YES" : "NO") << endl;
  cout << (k_pal("axxbababa", 2) ? "YES" : "NO") << endl;
  return 0;
}

- finalpatch July 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
using namespace std;

bool k_pal_helper(const string& input, unsigned k, unsigned l, unsigned r)
{
  cout << input << ": k=" << k << " l=" << l << " r=" << r << endl;
  
  if (r <= l)
    return true;
  
  if (input[l] == input[r])
    return k_pal_helper(input, k, l+1, r-1);
  
  if (k == 0)
    return false;

  // k > 0, first try delete from left
  bool result = k_pal_helper(input, k-1, l+1, r);
  if (result)
    return true;
  
  // then try delete from right
  result = k_pal_helper(input, k-1, l, r-1);
  if (result)
    return true;
  
  return false;
}

bool k_pal(const string& input, unsigned k)
{
  return k_pal_helper(input, k, 0, input.size()-1);
}

int main()
{
  cout << (k_pal("abxxxca", 1) ? "YES" : "NO") << endl;
  cout << (k_pal("abxxxca", 2) ? "YES" : "NO") << endl;
  cout << (k_pal("abxxca", 1) ? "YES" : "NO") << endl;
  cout << (k_pal("abxxca", 2) ? "YES" : "NO") << endl;
  cout << (k_pal("axxbababa", 2) ? "YES" : "NO") << endl;
  return 0;
}

- finalpatch July 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def kpalindrome(str, k)
  i = edits = 0
  j = str.size - 1
  cache = {}

  res = _kpal(str, cache, k, edits, i, j)
  res <= k
end

def _kpal(str, cache, k, edits, i, j)
  return edits if edits > k
  return edits if i >= j
  cached = cache[[i, j]]
  return cached if cached


  edits = 
    if str[i] == str[j]
      _kpal(str, cache, k, edits, i + 1, j - 1)
    else
      edits += 1
      left = _kpal(str, cache, k, edits, i + 1, j)
      right = _kpal(str, cache, k, edits, i, j - 1)
      [left, right].min
    end

  cache[[i, j]] = edits
  edits
end

p kpalindrome("axxbababa", 2)

Recursive Ruby solution with caching. O(n) = k^2

- fl00r August 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def kpalindrome(str, k)
  i = edits = 0
  j = str.size - 1
  cache = {}

  res = _kpal(str, cache, k, edits, i, j)
  res <= k
end

def _kpal(str, cache, k, edits, i, j)
  return edits if edits > k
  return edits if i >= j
  cached = cache[[i, j]]
  return cached if cached


  edits = 
    if str[i] == str[j]
      _kpal(str, cache, k, edits, i + 1, j - 1)
    else
      edits += 1
      left = _kpal(str, cache, k, edits, i + 1, j)
      right = _kpal(str, cache, k, edits, i, j - 1)
      [left, right].min
    end

  cache[[i, j]] = edits
  edits
end

p kpalindrome("axxbababa", 2)

- fl00r August 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can simply iterate from both sides and count the non-matching occurrences

public class Palindrome {
    static boolean isKthPalindrome(String s, int k) {
        if (s == null)
            return false;
        if (s.length() == 1)
            return true;
        char[] chars = s.toCharArray();
        int count = 0;
        for (int i = 0, j = chars.length - 1; j > i;) {
            if (chars[i] == chars[j]) {
                i++;
                j--;
                continue;
            }
            if (count == k)
                return false;
            count++;
            if (i + 1 < j && chars[i + 1] == chars[j]) {
                i++;
            } else {
                j--;
            }
        }
        return true;
    }
    
    static void printIsKthPalindrome(String s, int k) {
        boolean ret = isKthPalindrome(s, k);
        System.out.println(s + " : " + (ret ? "YES" : "NO"));
    }

    public static void main(String[] args) {
        printIsKthPalindrome("axbcybas", 3);
    }
}

- HG November 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean kPelindromeTest(String str,String strReverse,int k){


Map<Character,Integer> mapTest=new HashMap<Character,Integer>();
int count=0;
for(int i=0;i<str.length();i++){

if(str.charAt(i)!=(strReverse.charAt(i))){
if(mapTest.get(strReverse.charAt(i))!=null){
continue;
}

count++;
mapTest.put(str.charAt(i), i);
}

}
System.out.println(count);
if(count==k)
return true;
else
return false;


}

- mesh October 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean kPelindromeTest(String str,String strReverse,int k){
		
		
		Map<Character,Integer> mapTest=new HashMap<Character,Integer>();
		int count=0;
		for(int i=0;i<str.length();i++){
			
				if(str.charAt(i)!=(strReverse.charAt(i))){
					if(mapTest.get(strReverse.charAt(i))!=null){
						continue;
					}
					
					count++;
					mapTest.put(str.charAt(i), i);
				}
			
		}
		System.out.println(count);
		if(count==k)
			return true;
		else
			return false;

}

- mesh October 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean kPelindromeTest(String str,String strReverse,int k){
		
		
		Map<Character,Integer> mapTest=new HashMap<Character,Integer>();
		int count=0;
		for(int i=0;i<str.length();i++){
			
				if(str.charAt(i)!=(strReverse.charAt(i))){
					if(mapTest.get(strReverse.charAt(i))!=null){
						continue;
					}
					
					count++;
					mapTest.put(str.charAt(i), i);
				}
			
		}
		System.out.println(count);
		if(count==k)
			return true;
		else
			return false;
		
		
	}

- mesh October 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean kPelindromeTest(String str,String strReverse,int k){
		
		
		Map<Character,Integer> mapTest=new HashMap<Character,Integer>();
		int count=0;
		for(int i=0;i<str.length();i++){
			
				if(str.charAt(i)!=(strReverse.charAt(i))){
					if(mapTest.get(strReverse.charAt(i))!=null){
						continue;
					}
					
					count++;
					mapTest.put(str.charAt(i), i);
				}
			
		}
		System.out.println(count);
		if(count==k)
			return true;
		else
			return false;
		
		
	}and

- Anonymous October 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i got the solution

- mesh October 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

and Map<Character,Integer> mapTest=new HashMap<Character,Integer>();
		int count=0;
		for(int i=0;i<str.length();i++){
			
				if(str.charAt(i)!=(strReverse.charAt(i))){
					if(mapTest.get(strReverse.charAt(i))!=null){
						continue;
					}
					
					count++;
					mapTest.put(str.charAt(i), i);
				}
			
		}
		System.out.println(count);
		if(count==k)
			return true;
		else
			return false;

- mesh October 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Alright, here it is: an actual—dare I say it—working O(n*k) time & space algorithm, written in Javascript:

function kPalindrome(string, k=0)
{
	const l = string.length
	const s = 2 * k

	const M = new Array(l + 1)

	for (let i = 0; i <= l; i++)
	{
		M[i] = new Array(s + 1)

		for (let j = 0; j <= s; j++)
		{
			const t = i + j - k
			const u = i - 1
			const v = l - t

			M[i][j] = (i === 0) ? t : Math.min(

				// Deletion
				j < s ?
					M[i - 1][j + 1] + 1 :
					Number.POSITIVE_INFINITY,

				// Insertion
				j > 0 ?
					M[i][j - 1] + 1 :
					Number.POSITIVE_INFINITY,

				// Substitution
				v >= 0 && v < l ?
					M[i - 1][j] + 2 * (string[u] !== string[v]) :
					Number.POSITIVE_INFINITY
			)
		}
	}

	return (M[l][k] >> 1) <= k
}

First approach was the obvious recursive solution. You're looking at an exponential time complexity so throw that out.

Second approach (the above) uses a modification of the edit distance algorithm. It seems the top answer also uses this approach, but makes a couple of goofs. First, it still uses O(n^2) space. Second, is that they're incorrectly handled substitutions. Substitutions aren't neglected by simply copying the upper left diagonal value – you still have to handle them somehow. You can do that by pretending a substitution is an insertion and a deletion in one step. So that comes out with a cost of two, rather than one. Finally, they're not returning a boolean, but the final cost. This cost is going to be twice what it needs to be, as it has to delete all letters, then insert them all, to get the reverse string. So they need to cut that sucker in half and compare it to k!

- Benjamin Fleming September 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Alright, here it is: an actual—dare I say it—working O(n*k) time & space algorithm, written in Javascript:

function kPalindrome(string, k=0)
{
	const l = string.length
	const s = 2 * k

	const M = new Array(l + 1)

	for (let i = 0; i <= l; i++)
	{
		M[i] = new Array(s + 1)

		for (let j = 0; j <= s; j++)
		{
			const t = i + j - k
			const u = i - 1
			const v = l - t

			M[i][j] = (i === 0) ? t : Math.min(

				// Deletion
				j < s ?
					M[i - 1][j + 1] + 1 :
					Number.POSITIVE_INFINITY,

				// Insertion
				j > 0 ?
					M[i][j - 1] + 1 :
					Number.POSITIVE_INFINITY,

				// Substitution
				v >= 0 && v < l ?
					M[i - 1][j] + 2 * (string[u] !== string[v]) :
					Number.POSITIVE_INFINITY
			)
		}
	}

	return (M[l][k] >> 1) <= k
}

First approach was the obvious recursive solution. You're looking at an exponential time complexity so throw that out.

Second approach (the above) uses a modification of the edit distance algorithm. It seems the top answer also uses this approach, but makes a couple of goofs. First, it still uses O(n^2) space. Second, is that they're incorrectly handled substitutions. Substitutions aren't neglected by simply copying the upper left diagonal value – you still have to handle them somehow. You can do that by pretending a substitution is an insertion and a deletion in one step. So that comes out with a cost of two, rather than one. Finally, they're not returning a boolean, but the final cost. This cost is going to be twice what it needs to be, as it has to delete all letters, then insert them all, to get the reverse string. So they need to cut that sucker in half and compare it to k!

- Benjamin Fleming September 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Until K == 0:
recursively try to remove each char and see if the rest is a palindrome.


Python:

def is_palindrome(s):
    ll = len(s)
    for i in range(ll/2):
        if s[i] != s[ll-1-i]:
            return False
    return True

def is_K_palindrome(s, K):
    # Recursion:
    # 1) for each char, remove it, see if the rest is a palindrome.
    # 2) if not lucky: try next until K == 0

    if is_palindrome(s):
        print "This one is:", s
        return True

    if K == 0:
        # return is_palindrome(s) --- just checked : it is not... 
        return False

    for i in range(len(s)):
        prev, next = s[:i], s[i+1:]
        if is_K_palindrome(prev+next, K-1):
            return True

    return False

- Mabooka September 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's something even better: O(nk) time and O(k) space

function kPalindrome(string, k=0)
{
	const l = string.length
	const s = 2 * k

	const R = [ new Array(s + 1), new Array(s + 1) ]
	let p = 1

	for (let i = 0; i <= l; i++)
	{
		const q = p ^ 1

		for (let j = 0; j <= s; j++)
		{
			const t = i + j - k
			const u = i - 1
			const v = l - t

			R[q][j] = i === 0 ? t : Math.min(
				j < s ? R[p][j + 1] + 1 : Infinity, // Deletion
				j > 0 ? R[q][j - 1] + 1 : Infinity, // Insertion
				v >= 0 && v < l && string[u] === string[v] ? R[p][j] : Infinity // Substitution
			)
		}

		p = q
	}

	return (R[p][k] >> 1) <= k

}

- Benjamin Fleming September 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find Longest palindromic sub-sequence of the string and ( length_of_string - length_of_LPS ) > given_k
return "NO". else return "YES". O(n^2).

- sravanthreddy911 October 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

deleteIndex :: Int -> [Char] -> [Char]
deleteIndex i xs =
  List.take (i - 1) xs <> List.drop i xs

zeroPalindrome :: [Char] -> Bool
zeroPalindrome xs =
  let
    n =
      length xs `div` 2

    (as, bs) =
      List.splitAt n xs

  in
    as == List.take n (List.reverse bs)

kCombination :: Int -> Int -> [[Int]]
kCombination k n =
  fmap (List.take k) (List.permutations [0..n])

kPalindrome :: Int -> [Char] -> Bool
kPalindrome 0 xs =
  zeroPalindrome xs

kPalindrome k xs =
  let
    delete indices s =
      case indices of
        [] ->
          s
        i : ixs ->
          delete ixs (deleteIndex i s)

    go =
      List.any zeroPalindrome $
        [ ys
        | ys <- [ delete is xs
                | is <- kCombination k (length xs)
                ]
        ]
  in
    -- C = C(0) + ... + C(k)
    -- C(i) = (C(0) * i)!
    -- C = O(k!) is what we need to improve
    -- (there is no way to check a 0-palindrome in better than O(n))
    kPalindrome (k-1) xs || go

-- instead of finding a palindrome, let's only check
-- that it exists. O(n)
kZeroPalindrome :: Int -> [Char] -> Bool
kZeroPalindrome k s =
  let
    n =
      length s `div` 2

    (as, bs) =
      List.splitAt n s

    diff (x:xs) (y:ys) =
      if x == y then 0 else 2 +
        diff xs ys
    diff [] [] =
       0
    diff [] [_] =
       0
    diff [_] [] =
       0
    diff xs ys =
       List.length xs + List.length ys
  in
    diff as (List.reverse bs) < k

- Maddie November 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby, with backtracking. O(N*K) time (it is a large overstatement), O(N+K) space (N only for inputs, O(K) space used in the function)

Uses the typical double cursor (one from start and another from end), and stores the jump points to be able to backtrack in case the jump did not get to a solution.

-> (s, k) {
    i = 0
    j = s.length - 1
    backtrack = []
    loop do
        return 'YES' if i == j
        if s[i] == s[j]
            i += 1
            j -= 1
            next
        else
            if backtrack.length < k
                backtrack.unshift [:left, i, j]
                i += 1
                next
            else        
                backtrack = backtrack.drop_while { |side, _, _| side == :right }
                break if backtrack.empty?
                _, i, j = backtrack.shift
                backtrack.unshift [:right, i, j]
                j += 1
                next
            end
        end
    end
    return 'NO'
}

- saverio.trioni July 13, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive solution in C++

bool isKPalendrome(const char *S, const char *EndS, int K)
{
  for ( ; S < EndS; S++, EndS--)
  {
    if (*S != *EndS)
    {
      if (!K) // No more chars can be removed - fail
        return false;

      // Have to drop either the left or right, so try both scenarios in recursion
      return isKPalendrome(S + 1, EndS, K - 1) || isKPalendrome(S, EndS - 1, K - 1);
    }
  }

  return true;
}

- Luc September 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function kPelindromeTest(str, misses) {
  if (misses < 0) return false;
  if (str.length <= 1) return true;

  const len = str.length;
  if (str[0] === str[len - 1]) {
    return almostPali(str.substring(1, len - 1), misses);
  } else{
    return almostPali(str.substring(1, len), misses - 1) || almostPali(str.substring(0, len - 1), misses - 1);
  }
}

- yairniz November 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

isKPalindrome(k : number, s : string) {
   O(n + k^2)
   let start = 0;
   let end = s.length -1;
   while (true) {
      if ((end - start) <= 1) 
         return k == 0;
      if (s[start] == s[end - 1]) {
         start += 1;
         end -= 1;
         continue;
      }
      for (let d = 1; true; d += 1) {
         // n+k^2
         if (d > k)
            return false;
         if (start + d == end - 1) 
            return d == k || d + 1 == k;
         for (let e = 0; true; e += 1) {
            if (e > d)
               break;
            assert(e <= d);
            if (s[start + e] == s[end - 1 - (d - e)]) {
               k -= d;
               start += e;
               end -= (d - e);
               goto Pass;
            }
         }
         continue;
      Pass:
         break;
      }
   }
}

- xiongmao December 08, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean kPali(String str, int k) {
	kPali(str, 0, str.length - 1, k);
}

private boolean kPali(String str, int ptrL, int ptrR, int k) {
	return ptrL >= ptrR ||
		(str.charAt(ptrL) == str.charAt(ptrR) && kPali(str, ptrL + 1, ptrR - 1, k)) ||
		(k > 0 && (kPali(str, ptrL + 1, ptrR, k - 1) || kPali(str, ptrL, ptrR - 1, k - 1));
}

- liorkup January 30, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

python

def is_k_palindrome(s, k):
	if 0<=k<=30 and len(s) <= 20000:
		for i in range(len(s)):
			sub_s = s[:i] + s[i+k:]
			if sub_s == sub_s[::-1]:
				print('yes')
				print(sub_s)
			else:
				print('no')
				print(sub_s)

- pro100Istomin1988 April 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!python3

def is_palindrom_iter(s, k):
    stack = [(0, len(s)-1, k)]
    while stack:
        lo, hi, k = stack.pop()
        if lo >= hi:
            return True
        if s[lo] == s[hi]:
            stack += [(lo+1, hi-1, k)]
            continue
        if k == 0:
            continue
        stack += [(lo+1, hi, k-1)]
        stack += [(lo, hi-1, k-1)]
    return False

- Art May 31, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!python3

def is_palindrom_iter(s, k):
    stack = [(0, len(s)-1, k)]
    while stack:
        lo, hi, k = stack.pop()
        if lo >= hi:
            return True
        if s[lo] == s[hi]:
            stack += [(lo+1, hi-1, k)]
            continue
        if k == 0:
            continue
        stack += [(lo+1, hi, k-1)]
        stack += [(lo, hi-1, k-1)]
    return False

- Art May 31, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

## After removing whiespace removd and converting to lower case, 
## a palindrome has at most letter with odd count
## Python 3 implementation

from collections import Counter
def is_kplaindrome(s,k):
    '''Prints "YES" if S is a k-palindrome; otherwise prints "NO"'''
    
    ## Check input
    if not isinstance(s,str):
        raise TypeError('Input s in not string type')
    if not isinstance(k,int):
        raise TypeError('Input k is not integer')
    if (k<0):
        raise ValueError('k should be a positive integer')
    
    counter = Counter(s.replace(' ','').lower())
    is_odd_couter  = (v%2 != 0 for v in counter.values())  # generator expression
    count_odds = sum(is_odd_couter)
    result = count_odds <= k+1
    if result:
        print('YES')
    else:
        print('NO')
    return result


def test_is_kplaindrome_inputs():
    try:
        is_kplaindrome(1,1)
    except TypeError as e:
        print(type(e),e)
    
    try:
        is_kplaindrome('ab','a')
    except TypeError as e:
        print(type(e),e)
        
    try:
        is_kplaindrome('ab',-1)
    except ValueError as e:
        print(type(e),e)

def test_is_kplaindrome():
    assert is_kplaindrome('a',0) == True
    assert is_kplaindrome('ab',1) == True
    assert is_kplaindrome('aa1234',5) == True
    assert is_kplaindrome('aa1234',5) == True
    assert is_kplaindrome('aa1234',3) == True
    assert is_kplaindrome('aa1234',2) == False
    assert is_kplaindrome('abxa',1) == True
    assert is_kplaindrome('abdxa',1) == False

help(is_kplaindrome)
test_is_kplaindrome_inputs()
test_is_kplaindrome()

- AR August 09, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# A k-palindrome is a string which transforms into a palindrome on removing at most k characters.
#
# Given a string S, and an interger K, print "YES" if S is a k-palindrome; otherwise print "NO".
# Constraints:
# S has at most 20,000 characters.
# 0<=k<=30
#
# Sample Test Case#1:
# Input - abxa 1
# Output - YES
# Sample Test Case#2:
# Input - abdxa 1
# Output - No
import string
import random


def lev_distance_modified(a: list, b: list, max_dist: int, dist: int) -> int:
    # See if we can terminate early
    if dist > max_dist:
        res = dist
    elif len(a) == 0:
        res = len(b)
    elif len(b) == 0:
        res = len(a)
    elif a[0] == b[0]:
        res = lev_distance_modified(a[1:], b[1:], max_dist, dist)
    else:
        res = min([
            lev_distance_modified(a, b[1:], max_dist, dist + 1),  # 1 delete from b
            lev_distance_modified(b, a[1:], max_dist, dist + 1),  # 1 delete from a
            lev_distance_modified(a[1:], b[1:], max_dist, dist + 2)])  # 2 deletes one for each side

    return res


def num_palindrome_deletes(s: str, max_dist: int) -> str:
    l = list(s)
    r = list(reversed(l))
    return lev_distance_modified(l, r, max_dist, 0)


def is_k_palindrome(s: str, k: int) -> str:
    return num_palindrome_deletes(s, k * 2) <= k * 2


print(is_k_palindrome("abxa", 1))
print(is_k_palindrome("abdxa", 1))

s = "".join(random.choices(string.ascii_letters, k=20000))
print(is_k_palindrome(s, 6))

- Vassili Gorshkov April 10, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I made a C# method for it. This appears to work and I BELIEVE it'll cover cases that result from larger strings also. Little bit lengthy, but recursive method seemed most logical to handle the total number of removed characters. There's obviously driver code, but its not all that important.

public static int testPalin(string palin)
        {
            if (start == end || start > end) { return 0; }
            else if (palin[start] == palin[end])
            {
                start++; end--;
                return testPalin(palin);
            }
            else
            {
                int depth = 1;
                while (depth <= max)
                {
                    if (palin[start + 1 + (depth - 1)] == palin[end - (depth - 1)])
                    {
                        start += depth + depth - 1;
                        end -= depth - 1;
                        return 2 * depth - 1 + testPalin(palin);
                    }
                    else if (palin[start + (depth - 1)] == palin[end - 1 - (depth - 1)])
                    {
                        start += depth - 1;
                        end -= depth + depth - 1;

                        return 2 * depth - 1 + testPalin(palin);
                    }
                    else if (palin[start + 1 + (depth - 1)] == palin[end - 1 - (depth - 1)])
                    {
                        start += depth + depth - 1;
                        end -= depth + depth - 1;
                        return 2 * depth + testPalin(palin);
                    }
                    else if (depth < max)
                        depth++;
                    else
                        return depth;   //No palindrome possible with current max removable nums.
                }

            }
            return 1; //The code gets fussy about making sure there's a return, so I put it in to shit it up. 
        }

- brennahan August 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

I tested it, you are right it will not work with "axxba". So I am removing it.

- Ajeet August 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code does not work. Counter-example: "axxbababa", k = 2. Answer is True, but your code gives False

- Miguel Oliveira August 29, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More