:orphan:

Valid Palindrome
================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/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``\ :sup:```5```
- ``s`` consists only of printable ASCII characters.

.. highlight:: python

Pattern
-------
Two Pointers, String

Solution
--------
First, we convert ``s`` to all lowercase. Rather than remove all
non-alphanumeric characters, we can ignore them when checking if ``s`` is a
palindrome. We do this by using two pointers ``i`` and ``j`` at the beginning
of ``s`` and at the end of ``s``. When both pointers are on non-alphanumeric
characters, move them inwards.

Code
----

.. literalinclude:: ../problems/easy/valid-palindrome/valid_palindrome__two_pointers.py
    :language: python
    :lines: 14-

Test
----
>>> from valid_palindrome__two_pointers import isPalindrome
>>> isPalindrome('A man, a plan, a canal: Panama')
True
>>> isPalindrome('race a car')
False
>>> isPalindrome(' ')
True
>>> isPalindrome('0P')
False

Complexity
----------
| :math:`n` is the length of ``s``.
| Time: :math:`O(n)` — single pass through ``s``.
| Auxiliary Space: :math:`O(n)` — lowercase copy

.. autofunction:: valid_palindrome__two_pointers.isPalindrome