Difficulty: Easy

A palindrome is a word that reads the same forward and backward. 

This problem is a bit different from a normal palindrome check. A normal palindrome check problem can be solved simply by checking if the reverse of the string is the same as the string. Which in python is a simple one-liner:

class Solution:
  def isPalindrome(self, s: str) -> bool:         
    return s == s[::-1]

This solution is still very inefficient, as reversing the string with s[::-1] costs O(n) time and it also creates a string costing O(n) space as well. But, this problem requires every uppercase character to be converted into lowercase, and non-alphanumeric characters are not included in the palindrome check.

So the most efficient way to solve this problem is using two pointers. The left (L) pointer starts at the first index and the right (R) pointer starts at the last index. Then using we move both pointers toward the center until L and R pointers pass each other. We move both pointers 1 increment together, but only if both values are the same. If any of the pointers reaches a non-alphanumeric character we only move that pointer, essentially skipping the value. When we perform equal checks we make sure that both characters are converted to lower case, and if they are not equal the string is not a palindrome and we return false. Finally, once the iteration completes we return True.

An edge case is if the string is of size 0 (which is not possible in LeetCode), but this solution works for this as well. Since, L=0 and R=-1, so the loop never begins and the function returns True. This is correct because an empty string is a palindrome.

Time Complexity: O(n)

Space Complexity: O(1)

class Solution:
  def isPalindrome(self, s: str) -> bool:
    L = 0
    R = len(s) - 1
     
    while L <= R:
      if not s[L].isalnum():
        L += 1
      elif not s[R].isalnum():
        R -= 1
      elif s[L].lower() != s[R].lower():
        return False
      else:
        L += 1
        R -= 1    
    return True