Solutions

1. Brute Force

O(n²) time | O(n) space

Intuition

We can remove each character from the string one by one and check whether what is left is a palindrome.

To check whether a string is a palindrome we will compare it with its reverse.

Algorithm

Return true if the string is equal to its reverse.
Iterate through the loop from the first character to the last character with i index.
Create a new string without the character at i and return true if it is equal to its reverse.
Return false when the loop finishes.

012345

abcbad ≠ dabcba

1 / 8

Code

def validPalindrome(s: str) -> bool:
    if isPalindrome(s):
        return True
    for i in range(len(s)):
        if isPalindrome(s[:i] + s[i + 1:]):
            return True
    return False


def isPalindrome(text: str) -> bool:
    return text == text[::-1]

/**
 * @param {string} s
 * @returns {boolean}
 */
var validPalindrome = function (s) {
  if (isPalindrome(s)) return true
  for (let i = 0; i < s.length; i++) {
    if (isPalindrome(s.slice(0, i) + s.slice(i + 1))) return true
  }
  return false
}

var isPalindrome = function (text) {
  return text === [...text].reverse().join('')
}

class Solution {
    public boolean validPalindrome(String s) {
        if (isPalindrome(s)) return true;
        for (int i = 0; i < s.length(); i++) {
            if (isPalindrome(s.substring(0, i) + s.substring(i + 1))) return true;
        }
        return false;
    }

    private boolean isPalindrome(String text) {
        return text.equals(new StringBuilder(text).reverse().toString());
    }
}

2. Two Pointers

O(n) time | O(1) space

Intuition

We can compare the characters starting at both ends of the string and moving towards each other.

If all of the pairs are equal, it is a palindrome.

If one of the pairs differs, the only characters we might need to remove are the two in that pair. So we check both options, first without one of them and then without the other.

Algorithm

Create left and right integer variables with the start and end indexes of the string as initial values.
Iterate through the loop while left is less than right, moving left one step to the right and right one step to the left after each iteration.
If the characters at left and right differ:
- Compare the characters at both ends of the part from left + 1 to right, moving the ends towards each other, and return true if every pair is equal.
- Do the same with the part from left to right - 1, and return true if every pair is equal.
- Return false in all other cases.
Return true when the loop finishes.

left right

a ≠ d

1 / 5

Code

def validPalindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return (isPalindrome(s, left + 1, right)
                    or isPalindrome(s, left, right - 1))
        left += 1
        right -= 1
    return True


def isPalindrome(s: str, left: int, right: int) -> bool:
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

/**
 * @param {string} s
 * @returns {boolean}
 */
var validPalindrome = function (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
}

var isPalindrome = function (s, left, right) {
  while (left < right) {
    if (s[left] !== s[right]) return false
    left++
    right--
  }
  return true
}

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        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;
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
}