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

Comment hidden because of low score. Click to expand.
0

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

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

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

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

OOops, ignore the previous comment. It is correct.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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];

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Does not work for

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

AND MANY OTHER CASES

Comment hidden because of low score. Click to expand.
0

@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

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");
}``````

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

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

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);
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
2
of 2 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++)

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])
else
}
}

}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@Miguel. Try proving that it works.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@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?

Comment hidden because of low score. Click to expand.
0

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

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)

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);
}
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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?

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?

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);
}
}

}``````

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)

Comment hidden because of low score. Click to expand.
0

How could I indent?

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

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

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();
}

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?

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);
}``````

Comment hidden because of low score. Click to expand.
0

@maks - this does not work

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

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)

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

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

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;
}
}``````

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;
}``````

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

I agreed! :) Modified comments accordingly.

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";
}``````

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;
}``````

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";

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

}``````

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);
}``````

Comment hidden because of low score. Click to expand.
0

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.

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.

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;
}``````

Comment hidden because of low score. Click to expand.
0

Line 6 is

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

actually.

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

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

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

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

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

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

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]);
}
}

}``````

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

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");
}``````

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;
}``````

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;
}``````

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;
}``````

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

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

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);
}
}``````

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;

}

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;``````

}

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;

}``````

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

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

i got the solution

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;``````

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!

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!

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

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

}

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

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

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'
}``````

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;
}``````

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);
}
}``````

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;
}
}
}``````

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));
}``````

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

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

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

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()``````

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

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

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.

Comment hidden because of low score. Click to expand.
0

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

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.

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