# Valid Palindrome
**Difficulty:** EASY
[External](https://leetcode.com/problems/valid-palindrome)
Canonical: https://scaleengineer.com/dsa/problems/valid-palindrome
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [American Express](https://scaleengineer.com/companies/american-express), [Cadence](https://scaleengineer.com/companies/cadence), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cisco](https://scaleengineer.com/companies/cisco), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [SAP](https://scaleengineer.com/companies/sap), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Shopee](https://scaleengineer.com/companies/shopee), [Spotify](https://scaleengineer.com/companies/spotify), [TikTok](https://scaleengineer.com/companies/tiktok), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Wipro](https://scaleengineer.com/companies/wipro), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Turing](https://scaleengineer.com/companies/turing), [Zenefits](https://scaleengineer.com/companies/zenefits), [RBC](https://scaleengineer.com/companies/rbc), [Wayfair](https://scaleengineer.com/companies/wayfair), [Axon](https://scaleengineer.com/companies/axon), [Bank of America](https://scaleengineer.com/companies/bank-of-america), [VK](https://scaleengineer.com/companies/vk), [Toast](https://scaleengineer.com/companies/toast)
---
## Problem
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 * 105`
* `s` consists only of printable ASCII characters.

# Approaches
## Filter, Reverse, and Compare
This approach involves creating a new string by filtering out non-alphanumeric characters and converting all letters to lowercase. Then, this new string is compared with its reversed version to determine if it's a palindrome.
**Time:** O(N) · **Space:** O(N)
**Pros:** Simple and easy to understand.; Separates the concerns of filtering and palindrome checking.
**Cons:** Inefficient in terms of space. It requires creating at least one, and in this specific implementation, two new strings whose size can be up to the original string's length.
### Explanation
First, we iterate through the input string `s`. We use a `StringBuilder` to build a new string. For each character in `s`, we check if it's a letter or a digit using `Character.isLetterOrDigit()`. If it is, we convert it to lowercase using `Character.toLowerCase()` and append it to our `StringBuilder`. After iterating through the entire input string, we have a "cleaned" version. We then create a reversed version of this cleaned string. Finally, we compare the cleaned string with its reversed counterpart. If they are identical, the original string is a palindrome.

```java
class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder filteredString = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                filteredString.append(Character.toLowerCase(c));
            }
        }
        
        String original = filteredString.toString();
        String reversed = filteredString.reverse().toString();
        
        return original.equals(reversed);
    }
}
```
### Algorithm
1. Initialize an empty `StringBuilder`, let's call it `filteredBuilder`.
2. Iterate through each character `c` of the input string `s`.
3. If `c` is an alphanumeric character:
    a. Convert `c` to its lowercase equivalent.
    b. Append the lowercase character to `filteredBuilder`.
4. Convert `filteredBuilder` to a string, `filteredString`.
5. Create a new string, `reversedString`, which is the reverse of `filteredString`.
6. Compare `filteredString` and `reversedString`. If they are equal, return `true`. Otherwise, return `false`.

## Filtered String with Two Pointers
This method first filters the string to keep only alphanumeric characters (in lowercase), similar to the first approach. However, instead of creating a reversed copy, it uses a two-pointer technique on the filtered string to check for palindrome properties, which is more memory-efficient for the checking phase.
**Time:** O(N) · **Space:** O(N)
**Pros:** Still relatively simple to implement.; Slightly more efficient than the first approach as it avoids creating a second (reversed) string.
**Cons:** Still requires O(N) extra space to store the filtered string.
### Explanation
The initial step is identical to the previous approach: create a new `StringBuilder` by iterating through the input string `s`, and appending only the lowercase versions of alphanumeric characters. Once we have the cleaned string, we initialize two pointers: `left` at the beginning (index 0) and `right` at the end of the string. We then enter a loop that continues as long as `left` is less than `right`. Inside the loop, we compare the characters at the `left` and `right` pointers. If at any point the characters do not match, we know it's not a palindrome, and we can immediately return `false`. If the characters match, we move the pointers closer to the center by incrementing `left` and decrementing `right`. If the loop completes without finding any mismatches, it means the string is a palindrome, and we return `true`.

```java
class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder builder = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                builder.append(Character.toLowerCase(c));
            }
        }
        String filteredString = builder.toString();
        int left = 0;
        int right = filteredString.length() - 1;
        while (left < right) {
            if (filteredString.charAt(left) != filteredString.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
1. Initialize an empty `StringBuilder`, `filteredBuilder`.
2. Iterate through each character `c` of the input string `s`.
3. If `c` is an alphanumeric character, append its lowercase version to `filteredBuilder`.
4. Initialize two pointers: `left = 0` and `right = filteredBuilder.length() - 1`.
5. While `left < right`:
    a. If the character at `filteredBuilder.charAt(left)` is not equal to `filteredBuilder.charAt(right)`, return `false`.
    b. Increment `left` and decrement `right`.
6. If the loop finishes, return `true`.

## In-Place Two Pointers
This is the most optimal approach. It uses two pointers, one starting from the beginning of the string and one from the end, moving towards each other. It checks for palindromic properties in-place, without creating any new strings, thus achieving constant space complexity.
**Time:** O(N) · **Space:** O(1)
**Pros:** Highly efficient in terms of memory usage (O(1) space).; Performs the check in a single pass over the string.
**Cons:** The logic can be slightly more complex to write correctly due to the nested conditions for skipping non-alphanumeric characters.
### Explanation
We initialize two pointers, `left` at index 0 and `right` at the last index of the input string `s`. We loop as long as `left` is less than `right`. Inside the loop, we first advance the `left` pointer forward as long as it points to a non-alphanumeric character. Similarly, we move the `right` pointer backward as long as it points to a non-alphanumeric character. After these adjustments, both pointers should be pointing to alphanumeric characters (or they have crossed, ending the loop). We then compare the lowercase versions of the characters at the `left` and `right` pointers. If they are different, the string is not a palindrome, and we return `false`. If they are the same, we move both pointers one step closer to the center (`left++`, `right--`) and continue the process. If the loop completes, it means all corresponding alphanumeric characters matched, so the string is a palindrome, and we return `true`.

```java
class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right) {
            char leftChar = s.charAt(left);
            char rightChar = s.charAt(right);
            
            if (!Character.isLetterOrDigit(leftChar)) {
                left++;
            } else if (!Character.isLetterOrDigit(rightChar)) {
                right--;
            } else {
                if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)) {
                    return false;
                }
                left++;
                right--;
            }
        }
        return true;
    }
}
```
### Algorithm
1. Initialize two pointers: `left = 0` and `right = s.length() - 1`.
2. Loop while `left < right`.
3. Inside the loop, get the characters `leftChar` at `s[left]` and `rightChar` at `s[right]`.
4. If `leftChar` is not alphanumeric, increment `left` and continue to the next iteration.
5. If `rightChar` is not alphanumeric, decrement `right` and continue to the next iteration.
6. If both are alphanumeric, compare their lowercase versions.
    a. If `Character.toLowerCase(leftChar)` is not equal to `Character.toLowerCase(rightChar)`, return `false`.
7. If they are equal, move the pointers inward: increment `left` and decrement `right`.
8. If the loop completes, return `true`.

# Solutions
### CSharp

```csharp
public class Solution { public bool IsPalindrome ( string s ) { int i = 0 , j = s . Length - 1 ; while ( i < j ) { if (! char . IsLetterOrDigit ( s [ i ])) { ++ i ; } else if (! char . IsLetterOrDigit ( s [ j ])) { -- j ; } else if ( char . ToLower ( s [ i ++]) != char . ToLower ( s [ j --])) { return false ; } } return true ; } }
```

### Java

```java
class Solution {
public
  boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
      if (!Character.isLetterOrDigit(s.charAt(i))) {
        ++i;
      } else if (!Character.isLetterOrDigit(s.charAt(j))) {
        --j;
      } else if (Character.toLowerCase(s.charAt(i)) !=
                 Character.toLowerCase(s.charAt(j))) {
        return false;
      } else {
        ++i;
        --j;
      }
    }
    return true;
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @return {boolean} */ var isPalindrome = function (s) {
  let i = 0;
  let j = s.length - 1;
  while (i < j) {
    if (!/ [ a-zA-Z0-9 ] /.test(s[i])) {
      ++i;
    } else if (!/ [ a-zA-Z0-9 ] /.test(s[j])) {
      --j;
    } else if (s[i].toLowerCase() !== s[j].toLowerCase()) {
      return false;
    } else {
      ++i;
      --j;
    }
  }
  return true;
};

```

### CPP

```cpp
class Solution {
public:
  bool isPalindrome(string s) {
    int i = 0, j = s.size() - 1;
    while (i < j) {
      if (!isalnum(s[i])) {
        ++i;
      } else if (!isalnum(s[j])) {
        --j;
      } else if (tolower(s[i]) != tolower(s[j])) {
        return false;
      } else {
        ++i;
        --j;
      }
    }
    return true;
  }
};

```

### Python

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

```