Find out if we can get a palindrome

Question

For line S. We need to say whether we can do this on the palindrome by removing exactly one letter from it or not. I have an O (N ^ 2) approach by changing the Edit Distance.Is method their best way?

My approach:

int ModifiedEditDistance(const string& a, const string& b, int k) { int i, j, n = a.size(); int dp[MAX][MAX]; memset(dp, 0x3f, sizeof dp); for (i = 0 ; i < n; i++) dp[i][0] = dp[0][i] = i; for (i = 1; i <= n; i++) { int from = max(1, ik), 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]; } 

How to improve spatial complexity, since the maximum row size can go up to 10 ^ 5.

Please, help.

Example: let String be abc, then the answer will be “NO”, and if the string is “abbcbba” then the answer is “YES”

Answer 1

The main observation is that if the first and last characters are the same, you do not need to delete any of them; that xSTRINGx can be turned into a palindrome by deleting one letter if and only if STRING can (while STRING has at least one character in length).

You want to define a method (sorry Java syntax - I'm not a C ++ encoder):

 boolean canMakePalindrome(String s, int startIndex, int endIndex, int toRemove); 

which determines whether it is possible to make part of the line from startIndex to endIndex-1 in the palindrome by removing toRemove characters.

When you consider canMakePalindrome(s, i, j, r) , you can define it in terms of smaller issues like this:

• If ji is 1, then return true; if it is 0, then return true if and only if r is 0. Here it is indicated that a 1-character string is a palindrome regardless of whether you delete the character; a line with a length of 0 lines is a palindrome, but cannot be turned into one by deleting a character (because it cannot be deleted).
• If s[i] and s[j-1] same, then this is the same answer as canMakePalindrome(s, i+1, j-1, r) .
• If they differ from each other, then s[i] or s[j-1] must be deleted. If toRemove is zero, then return false because you have no characters to delete. If toRemove is 1, return true if either canMakePalindrome(s, i+1, j, 0) or canMakePalindrome(s, i, j-1, 0) . This is because you are now checking to see if it is already a palindrome if you delete one of these two characters.

Now it can be encoded quite easily, I think.

If you want to allow the deletion of more than one character, you should use the same idea, but use dynamic programming. When deleting only one character, dynamic programming will reduce the constant coefficient, but will not reduce the asymptotic time complexity (linear along the length of the line).

Answer 2

Psudocode (something like this I haven't tested at all).

It is based on detecting conditions in which you can delete a character, i.e.

• There is exactly 1 wrong character
• This is a palette (0 mismatch)

O (n) in time, O (1) in space.

  bool foo(const std::string& s) { int i = 0; int j = s.size()-1; int mismatch_count = 0; while (i < j) { if (s[i]==s[j]) { i++; j--; } else { mismatch_count++; if (mismatch_count > 1) break; //override first preference if cannot find match for next character if (s[i+1] == s[j] && ((i+2 >= j-1)||s[i+2]==s[j-1])) { i++; } else if (s[j-1]==s[i]) { j--; } else { mismatch_count++; break; } } } //can only be a palendrome if you remove a character if there is exactly one mismatch //or if a palendrome return (mismatch_count == 1) || (mismatch_count == 0); } 

Answer 3

Here's a (slightly incomplete) solution that takes O (n) time and O (1) space.

 // returns index to remove to make a palindrome; string::npos if not possible size_t willYouBeMyPal(const string& str) { size_t toRemove = string::npos; size_t len = str.length(); for (size_t c1 = 0, c2 = len - 1; c1 < c2; ++c1, --c2) { if (str[c1] != str[c2]) { if (toRemove != string::npos) { return string::npos; } bool canRemove1 = str[c1 + 1] == str[c2]; bool canRemove2 = str[c1] == str[c2 - 1]; if (canRemove1 && canRemove2) { abort(); // TODO: handle the case where both conditions are true } else if (canRemove1) { toRemove = c1++; } else if (canRemove2) { toRemove = c2--; } else { return string::npos; } } } // if str is a palindrome already, remove the middle char and it still is if (toRemove == string::npos) { toRemove = len / 2; } return toRemove; } 

On the left, as an exercise, what to do if you get this:

 abxyxcxyba 

Correct solution:

 ab_yxcxyba 

But you can lead a bad way:

 abxyxcx_ba 

Therefore, when you find that the “next” character on both sides is a possible solution, you need to evaluate both possibilities.

Answer 4

I wrote a sample with O (n) complexity, which works for the tests that I threw at it. Not so much: D The idea is to ignore the first and last letters if they are the same, deleting one of them if they are not, and discuss what happens when the string is small enough. The same result can be archived using a loop instead of recursion, which will save some space (which makes it O (1)), but it’s more difficult to understand and subject to a more serious IMO error.

 bool palindrome_by_1(const string& word, int start, int end, bool removed = false) // Start includes, end excludes { if (end - start == 2){ if (!removed) return true; return word[start] == word[end - 1]; } if (end - start == 1) return true; if (word[start] == word[end - 1]) return palindrome_by_1(word, start + 1, end - 1, removed); // After this point we need to remove a letter if (removed) return false; // When two letters don't match, try to eliminate one of them return palindrome_by_1(word, start + 1, end, true) || palindrome_by_1(word, start, end - 1, true); } 

Answer 5

Checking for a palidrome on one line is O (n). You can implement a similar algorithm than moving two pointers, one from the very beginning and the other from the end. Move each pointer until the characters match, and on the first mismatch, try to match which char you can skip, and keep moving both pointers until the other characters match. Watch for the first discrepancy. This is O (n).

Answer 6

I hope my algorithm goes without providing the code.

If the word a ₁ a ₂ .... a _n can be made a palindrome by removing _k , we can find k as follows:

If a ₁ ! = A _n , then the only possible k will be 1 or n. Just check if there is ₁ a ₂ .... a _n-1 or ₂ a ₃ .... a _n is a palindrome.

If a ₁ == a _n , the next step solves the same problem for ₂ .... a _{p-1sub>. So we have recursion.}

Answer 7

public static boolean pal (String s, int start, int end) {

  if(end-start==1||end==start) return true; if(s.charAt(start)==s.charAt(end)) return pal(s.substring(start+1, end),0,end-2); else{ StringBuilder sb=new StringBuilder(s); sb.deleteCharAt(start); String x=new String(sb); if(x.equals(sb.reverse().toString())) return true; StringBuilder sb2=new StringBuilder(s); sb2.deleteCharAt(end); String x2=new String(sb2); if(x2.equals(sb2.reverse().toString())) return true; } return false; } 

Answer 8

I tried the following: f and b are indices in which characters do not match

 int canwemakepal(char *str)//str input string { long int f,b,len,i,j; int retval=0; len=strlen(str); f=0;b=len-1; while(str[f]==str[b] && f<b)//continue matching till we dont get a mismatch { f++;b--; } if(f>=b)//if the index variable cross over each other, str is palindrome,answer is yes { retval=1;//true } else if(str[f+1]==str[b])//we get a mismatch,so check if removing character at str[f] will give us a palindrome { i=f+2;j=b-1; while(str[i]==str[j] && i<j) { i++;j--; } if(i>=j) retval=1; else retval=0; } else if(str[f]==str[b-1])//else check the same for str[b] { i=f+1;j=b-2; while(str[i]==str[j] && i<j) { i++;j--; } if(i>=j) retval=1; else retval=0; } else retval=0; return retval; } 

Answer 9

 I created this solution,i tried with various input giving correct result,still not accepted as correct solution,Check it n let me know if m doing anything wrong!! Thanks in advance. public static void main(String[] args) { Scanner s = new Scanner(System.in); int t = s.nextInt(); String result[] = new String[t]; short i = 0; while(i < t) { String str1 = s.next(); int length = str1.length(); String str2 = reverseString(str1); if(str1.equals(str2)) { result[i] = "Yes"; } else { if(length == 2) { result[i] = "Yes"; } else { int x = 0,y = length-1; int counter = 0; while(x<y) { if(str1.charAt(x) == str1.charAt(y)) { x++; y--; } else { counter ++; if(str1.charAt(x) == str1.charAt(y-1)) { y--; } else if(str1.charAt(x+1) == str1.charAt(y)) { x++; } else { counter ++; break; } } } if(counter >= 2) { result[i] = "No"; } else result[i]="Yes"; } } i++; } // Loop over for(int j=0; j<i;j++) { System.out.println(result[j]); } } public static String reverseString(String original) { int length = original.length(); String reverse = ""; for ( int i = length - 1 ; i >= 0 ; i-- ) reverse = reverse + original.charAt(i); return reverse; }