Facebook Interview Question
InternsCountry: India
Interview Type: Written Test
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 ??
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.
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
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.
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, 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 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
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
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
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.
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
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.
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];
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.
Does not work for
cout << ModifiedEditDistance("abdxa", "axdba", 1) << endl; // 4 > 2*1 - NO
AND MANY OTHER CASES
@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
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");
}
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;
}
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);
}
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;
}
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.
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
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.
It looks like. The reversal is maxlayalam, so the longest common subsequence is: malayalam, the lenght difference 1, so it works.
@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.
@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?
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)
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);
}
}
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);
}
}
}
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)
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)
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)
#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();
}
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?
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);
}
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)
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²)
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))
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;
}
}
@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;
}
// 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;
}
Hmm that's pure backtracking.
Dynamic programming implies that you're saving subproblems results somewhere (like a table) and reusing them later.
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";
}
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;
}
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";
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
}
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);
}
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.
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;
}
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
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
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)}}
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)
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
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
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]);
}
}
}
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");
}
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;
}
#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;
}
#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;
}
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
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)
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);
}
}
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;
}
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;
}
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;
}
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
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;
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!
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!
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
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
}
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
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'
}
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;
}
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);
}
}
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;
}
}
}
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));
}
## 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()
# 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))
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.
}
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:
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