> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/string/valid-palindrome.md).

# Valid Palindrome

{% hint style="info" %}
String, Two Pointers
{% endhint %}

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. The input string `s` consists only of printable ASCII characters.
2. The string `s` can be empty.
3. The string `s` can contain spaces, punctuation, and other non-alphanumeric characters.
4. The string `s` can contain both uppercase and lowercase letters.

**Questions to Clarify:**

1. **Case Sensitivity:** Should the palindrome check be case-sensitive or case-insensitive? The problem statement suggests it should be case-insensitive, but it would be good to confirm this.
2. **Non-Alphanumeric Characters:** Should non-alphanumeric characters be ignored when checking for a palindrome? The problem statement suggests they should be, but again, it would be good to confirm this.
3. **Null Input:** How should the function handle a null input? Should it return `true` (since a null string can be considered a special case of an empty string), `false`, or should it throw an exception?
4. **Large Inputs:** What is the maximum length of the input string `s`? This could affect the choice of algorithm, especially for very long strings.
5. **Performance Requirements:** Are there any performance requirements or constraints? For example, does the function need to run in a certain amount of time or use a certain amount of memory?

### Solutions

Please note that this function considers an empty string and a null string as palindromes, which is consistent with the definition of a palindrome. An empty string reads the same forward and backward, and a null string can be considered a special case of an empty string. However, some people might argue that a null string should not be considered a palindrome, so you might want to handle this case differently depending on your specific requirements.

**Approach – Brute Force Technique**

The code first converts the string to lowercase and filters out non-alphanumeric characters. It then checks each character from the start of the string to the middle against the corresponding character from the end. If it finds a pair of characters that don’t match, it immediately returns `false`. If it doesn’t find any mismatched pairs, it returns `true` after checking all pairs.

**Steps**

1. **Check if the string is not null:** The `if (s is not null)` statement checks if the input string `s` is not null. If `s` is null, the function will skip the rest of the code and return `true`.
2. **Convert to lowercase and filter out non-alphanumeric characters:** The `Span<char> str = s.ToLower().Where(c => char.IsLetterOrDigit(c)).ToArray();` statement does three things:
   * `s.ToLower()` converts all characters in the string `s` to lowercase.
   * `Where(c => char.IsLetterOrDigit(c))` filters out any characters that are not letters or digits.
   * `ToArray()` converts the result back into an array of characters.
3. **Check each character pair:** The `for (int i = 0; i < len / 2; i++)` loop iterates over each character in the first half of the string `str`. For each character, it checks if it is the same as the corresponding character from the end of the string. If the characters are not the same, the function immediately returns `false`.
4. **Return true if no mismatches are found:** If the function has checked all character pairs and hasn't found any mismatches, it returns `true`.

```csharp
public class Solution
{
    public bool IsPalindrome(string s)
    {
        if (s is not null)
        {
            // N times
            Span<char> str = s.ToLower().Where(c => char.IsLetterOrDigit(c)).ToArray();
            var len = str.Length;
            for (int i = 0; i < len / 2; i++) //log N times
            {
                if (str[i] != str[len - i - 1])
                    return false;
            }
        }
        return true;
    }
}
```

> Complexity

* **Time complexity**: `O(N)`
* **Space complexity**: `O(N)`

**Approach – Two Pointers Technique**

Two pointers to compare characters without creating a new string.

**Steps**

1. **Initialize two pointers:** The `int i = 0, j = s.Length - 1;` line initializes two pointers, `i` and `j`. `i` starts at the beginning of the string `s` and `j` starts at the end.
2. **Start of the loop:** The `while (i < j)` line starts a loop that continues as long as `i` is less than `j`. This means the loop will continue until the two pointers meet or cross each other.
3. **Skip non-alphanumeric characters from the start:** The `while (i < j && !Char.IsLetterOrDigit(s[i])) i++;` line inside the loop skips any non-alphanumeric characters from the start of the string. It does this by checking if the character at the `i`th position is a letter or digit, and if it's not, it increments `i` to move to the next character.
4. **Skip non-alphanumeric characters from the end:** The `while (i < j && !Char.IsLetterOrDigit(s[j])) j--;` line inside the loop skips any non-alphanumeric characters from the end of the string. It does this by checking if the character at the `j`th position is a letter or digit, and if it's not, it decrements `j` to move to the previous character.
5. **Compare characters:** The `if (Char.ToLower(s[i]) != Char.ToLower(s[j])) return false;` line inside the loop compares the characters at the `i`th and `j`th positions. If they are not the same, it returns `false`, indicating the string is not a palindrome.
6. **Move the pointers:** The `i++; j--;` lines inside the loop move the pointers towards each other. This prepares for the next iteration of the loop, where the next pair of characters will be compared.
7. **Return true:** The `return true;` line after the loop returns `true`, indicating the string is a palindrome. This line is only reached if all pairs of characters have been compared and no mismatches have been found.

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

> Complexity

* **Time complexity**: `O(N)`
* **Space complexity**: `O(1)`


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs-57.gitbook.io/data-structure-and-algorithms/problems/string/valid-palindrome.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.