Valid Palindrome II

Palindrome is a fascinating concept. The beauty lies in its simplicity: a word, phrase, or sequence of characters that reads the same backwards as forward. However, what happens when we introduce a little twist to this classic definition? What if we allow the removal of at most one character from the string to make it a palindrome? In this article, we will explore this intriguing problem. So, sit back, grab a cup of coffee, and let’s dive into the world of palindrome deletion!

Problem Statement:

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

---

Approach 1: Brute Force

So the idea is to generate all possible substrings by removing one character at a time from the given string and checking if any of the substrings are palindromes.

1. Base case: Check if the given input string is a palindrome or not.

2. After this, iterate through the input string and generate all the possible substrings by removing one character at a time.

3. Check if the substring is a palindrome, if yes, return True. Otherwise, continue with the iteration.

4. If none of the substrings are palindrome then return False.

// ES6 Arrow Function
const validPalindrome = s => {

    // Base Case
    if (isPalindrome(s)) {
        return true;
    }

    // Generate all possible substrings by removing one character at a time
    for (let i = 0; i < s.length; i++) {
        let substr = s.slice(0, i) + s.slice(i + 1);

        // Check if the substring is a palindrome
        if (isPalindrome(substr)) return true;
    }

    // If none of the substrings are palindromes, return false
    return false;
}

  // helper function to check if a string is a palindrome.
const isPalindrome = s => {
let left = 0;
let right = s.length - 1;

while (left < right) {
    if (s[left] !== s[right]) {
    return false;
    }
    left++;
    right--;
}

  return true;
}

Time Complexity: O(N³)

Space Complexity: O(N)

Note - This method is highly inefficient as we are generating all the possible substrings.

---

Approach 2: Two Pointers

1. In this approach, we initialize two pointers, one pointing to the start of the string and the other pointing to the end of the string, and comparing the characters at these pointers.

2. If the characters match, we increment the left pointer and decrement the right pointer.

3. If they don’t match, we can check if deleting either the character at the left pointer or the character at the right pointer would result in a palindrome.

4. If either of these new strings is a palindrome, we can return true.

5. Otherwise, we continue to check the characters at the pointers until we have checked all possible combinations.

// ES6 Arrow Function
const validPalindrome = s => {
    let left = 0, right = s.length - 1;

    while(left < right) {
        if(s[left] !== s[right]) {
            // check if deleting the char at the left pointer or right pointer would result in a palindrome.
            return isPalindrome(s.slice(left, right)) || isPalindrome(s.slice(left + 1, right + 1));
        }

        left++;
        right--;
    }

    return true;
}

// helper function to check if a string is a palindrome.
const isPalindrome = s => {
let left = 0;
let right = s.length - 1;

while (left < right) {
    if (s[left] !== s[right]) {
    return false;
    }
    left++;
    right--;
}

  return true;
}

Time Complexity: O(N)

Space Complexity: O(N)

---

Approach 3: Modified Two-Pointers

In the previous approach, we used the slice() operator on the input string and passed the resulting substring as an argument to the isPalindrome() function to check if the substring is a palindrome or not. However, this approach results in a linear space complexity of O(N), where N is the length of the input string, as a new substring is created in each iteration of the loop.

To achieve a constant space complexity, we can modify the isPalindrome() function to take the input string and the start and end indices as arguments, instead of creating a new substring using the slice() operator. By doing so, we can avoid the creation of new substrings and achieve a constant space complexity of O(1).

// ES6 Arrow Function
const validPalindrome = s => {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        if (s[left] !== s[right]) {
          return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
        }

        left++;
        right--;
    }

    return true;
}

// Helper function to check if a string is a palindrome or not
const isPalindrome = (s, left, right) => {
    while (left < right) {
      if (s[left] !== s[right]) {
        return false;
      }
      left++;
      right--;
    }

    return true;
}

Time Complexity: O(N)

Space Complexity: O(1)

---

And there you have it guys! We’ve explored different approaches, optimized our solutions, and hopefully had some fun along the way. Remember, when it comes to palindromes, sometimes it’s not about being perfect, it’s about being close enough. So don’t worry if you can’t quite make a palindrome out of your string, just delete a character and call it a day. After all, as they say in the world of palindromes, ‘A man, a plan, a canal, Panama!’.

I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 680