Valid Palindrome

---

Valid Palindrome: A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

---

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

---

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

---

Constraints:

• 1 <= s.length <= 2 * 10^5
• s consists only of printable ASCII characters.

---

Try this Problem on your own or check similar problems:

1. Palindrome Linked List
2. Valid Palindrome II

Solution:

Java

public boolean isPalindrome(String s) {
  int start = 0, end = s.length() - 1;
  while(start < end){
      char charStart = s.charAt(start), charEnd = s.charAt(end);
      if(!Character.isLetterOrDigit(charStart)){
        ++start;
        continue;
      }
      if(!Character.isLetterOrDigit(charEnd)){
        --end;
        continue;
      }
      if(Character.toLowerCase(charStart) != Character.toLowerCase(charEnd)) return false;
      ++start;
      --end;
  }
  return true;
}

JavaScript

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
  let start = 0;
  let end = s.length - 1;
  while (start < end) {
    const charStart = s.charAt(start);
    const charEnd = s.charAt(end);
    if (!isLetterOrDigit(charStart)) {
      ++start;
      continue;
    }
    if (!isLetterOrDigit(charEnd)) {
      --end;
      continue;
    }
    if (toLowerCase(charStart) !== toLowerCase(charEnd)) {
      return false;
    }
    ++start;
    --end;
  }
  return true;
};

function isLetterOrDigit(c) {
  return /[a-zA-Z0-9]/.test(c);
}

function toLowerCase(c) {
  return c.toLowerCase();
}

Python

class Solution:
    def isPalindrome(self, s: str) -> bool:
        start = 0
        end = len(s) - 1
        while start < end:
            char_start = s[start]
            char_end = s[end]
            if not char_start.isalnum():
                start += 1
                continue
            if not char_end.isalnum():
                end -= 1
                continue
            if char_start.lower() != char_end.lower():
                return False
            start += 1
            end -= 1
        return True

C++

class Solution {
public:
    bool isPalindrome(string s) {
        int start = 0, end = s.length() - 1;
        while (start < end) {
            char charStart = s[start], charEnd = s[end];
            if (!isalnum(charStart)) {
                ++start;
                continue;
            }
            if (!isalnum(charEnd)) {
                --end;
                continue;
            }
            if (tolower(charStart) != tolower(charEnd))
                return false;
            ++start;
            --end;
        }
        return true;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

We traverse through the whole string making the time complexity linear. This approach of using one pointer starting at the start of string and moving to the right, and the other starting and the end of string and moving to the left is called Two pointers approach and can be also used to check if a string is a palindrome. We iterate until the pointers are pointing to the same character, each time checking if the leftmost and rightmost characters are the same (when they're turned to lowercase). We skip checking if any of the pointers are pointing at a non-alphanumeric and we move the next character. If, however after skipping non-alphanumeric characters we have found a mismatch we know the string is not a palindrome and we return false otherwise we move the start pointer to the next right character, and end pointer to the next left character. If we manage to traverse the whole string (pointers meet at the middle, and then we have start == end, so we have to break from the loop) we know we checked all matching characters, so we return true as the string is a palindrome.