Valid Palindrome II

Given a string, check if the string can become palindrome by removing at-most one character from the string. The order of the characters in the string should remain same.

Example

"abca"
"abc"
"ymdadmt"

Output:
true // removing 'c' will make the string palindrome "aba"
false
false

Naïve solution: Valid Palindrome

Convert the string to array of characters, then iterate the array and in each iteration, filter out the element at current index and check if filtered array is palindrome or not.

const solution = (s) => {
  //split the string to array of characters
  const arr = s.split("");
  
  //iterate array and check if palindrome can be found
  for(let i = 0; i < arr.length; i++){
    
    //if palindrome is found
    if(isPalindrome(arr, i)){
      return true;
    }
  }
 
  //if no palindrome found
  return false;
}

const isPalindrome = (arr, index) => {
  // remove the character from the array
  const filtered = arr.filter((e, i) => i !== index);
  
  //length of the filtered array
  const n = filtered.length;
  
  //check if filtered array is palindrome
  for(let i = 0; i < n / 2; i++){
    if(filtered[i] !== filtered[n - i - 1]){
      return false;
    }
  }
  
  return true;
}

Input:
const str = "ab";
console.log(solution(str));

Output:
true

Time complexity: O(n ^ 2).
Space complexity: O(n).

---

Efficient solution

Conceptually this is how it works,

• Use two strings, one is normal and other is reversed.
• Iterate the original string and in each iteration, remove the i'th character from the beginning in the normal string and from rear in the reversed string.
• After removing the characters, if both the string matches that means they are palindrome.
• For example, consider this string "yadmda", now reversed string will be "admday", if we start iterating the original string and remove the character at 0'th index form start and end then we will get "admda" and admda, which are same.

// remove the i'th character from the string
const cut = (s, i) => s.substr(0, i) + s.substr(i + 1);

const solution = (s, n = s.length) => {
  // revesed string
  const reversed = s.split("").reverse().join("");
  
  //base case
  if(reversed === s){
     return true;
  }
  
  //iterate array and check if palindrome can be found
  for(let i = 0; i < n; i++){
    //index from start
    const start = i;
    
    //index from rear
    const end = n - i - 1;
    
    //get the updated string by removing the characters
    const nTransformed = cut(s, start);
    const rTransformed = cut(reversed, end);
    
    //if both string match, then it is palindrome
    if(nTransformed === rTransformed){
      return true;
    }  
  }
 
  //if no palindrome found
  return false;
}

Input:
const str = "ab";
console.log(solution(str));

Output:
true

Time complexity: O(n).
Space complexity: O(n).