> For the complete documentation index, see [llms.txt](https://yyloumike.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yyloumike.gitbook.io/leetcode/two-pointer/0125.-valid-palindrome.md).

# 0125. Valid Palindrome

Easy  |  Two Pointer  |  36 ms (95.59%),  14.7 MB (61.30%)

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Valid Palindrome](https://leetcode.com/problems/valid-palindrome/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0125-valid-palindrome)

Given a string `s`, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

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

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

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
**Two pointers**: One from the left (start) and the other from the right (end).
{% endhint %}

Note that **when `left > right` inside the while loop and the algorithm has not returned the False, we could return True directly.**
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def isPalindrome(self, s: str) -> bool:
        # (base case)
        if len(s) == 1: return True
        
        # ==================================================
        #  String + Two Pointer                            =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        left, right = 0, len(s) - 1
         
        while left < right:
            # consider only alphanumeric characters
            while left  < len(s) and not s[left].isalnum(): left += 1
            while right >= 0     and not s[right].isalnum(): right -= 1
                
            if left > right: return True
            
            # ignoring cases
            if s[left].lower() != s[right].lower(): return False
            
            left  += 1
            right -= 1
            
        return True
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(1)
     */
     
    public boolean isPalindrome(String s) {
        /* base case */
        if(s.length() == 1) return true;
        
        int left = 0, right = s.length() - 1;
        
        while(left < right) {
            while(left < s.length() && !Character.isLetterOrDigit(s.charAt(left))) left++;
            while(right >= 0 && !Character.isLetterOrDigit(s.charAt(right))) right--;
            
            if(left > right) return true;
            if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false;
            
            left++;
            right--;
        }
        
        return true;
    }
}
```

{% endtab %}
{% endtabs %}