In this tutorial, I am going to discuss a variation of palindrome questions valid palindrome II. In this problem, we can remove a character from a string to make it a palindrome.
Given a non-empty string, We may delete at most one character from a string. We have to write a code which checks whether we can make this string palindrome or not.
For example –
Example 1:
Input : “aba”
Output: true
This string is already palindrome. So we return true.
Example 2:
Input : “abca”
Output: true
This string is not a palindrome. But, if we delete either a character b or c from this string then the new string is a palindrome.
This problem is the trickiest version of valid palindrome problem. The tricky part is, if the given string is not a palindrome, then we can delete at most one character from a string. After deleting a character we have to check whether a new string is a palindrome or not.
Palindrome
A palindrome is a word, phrase or sequence that reads same backwards as forwards. For example – Nitin, madam, etc.
Let’s discuss how we can approach this problem.
Valid Palindrome II Video Tutorial
Valid Palindrome II – Java Code
The idea here is to traverse a string from both the ends using two pointers. Let’s say the two variables are left and right. The initial values of left and right are 0 and string length minus one.
Then run a loop and start comparing characters present at left and right index. If characters are equal then increment left pointer and decrement right pointer. If it is not equal then check whether a string is palindrome by deleting either the character present at left or right index.
If it’s not equal then return false, else return true.
The time complexity of this approach is O(n) and it’s space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
/* Delete at Most One Character to Make it a Palindrome - Java Code */ public boolean validPalindrome(String s) { //Declare two pointers int left = 0; int right = s.length()-1; /* Run a loop while left pointer is less than or equal to right pointer. */ while(left <= right) { if(s.charAt(left) != s.charAt(right)) { return isPalindrome(s, left+1, right) ||isPalindrome(s,left,right-1); } left++; right--; } return true; } //Logic to check palindrome private boolean isPalindrome(String s, int start, int end) { while(start <= end) { if(s.charAt(start) != s.charAt(end)) { return false; } start++; end--; } return true; } |
