> 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-ii.md).

# Valid Palindrome II

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

Given a string `s`, return true if the `s` can be palindrome after deleting **at most one character** from it.

Example 1:

```
Input: s = "aba"
Output: true
```

Example 2:

```
Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.
```

Example 3:

```
Input: s = "abc"
Output: false
```

**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` only lowercase letters.

**Questions to Clarify:**

1. **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.
2. **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?
3. **Large Inputs:** What is the maximum length of the input string `s`? This could affect the choice of algorithm, especially for very long strings.
4. **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

The provide string may or may not palindrome by default. We may need to delete at most one character to make string palindrome.

#### Approach - Brute Force Technique

In this problem is that I will use two pointers so that we can check if the string is palindrome after excluding one of the chars.

**Steps**

1. **Start of the function:** The `public bool ValidPalindrome(string s)` line defines a public function named `ValidPalindrome` that takes a string `s` as input and returns a boolean value.
2. **Start of the loop:** The `for (int i = 0; i < s.Length; i++)` line starts a loop that iterates over each character in the string `s`. The variable `i` is the loop counter and represents the index of the current character.
3. **Remove a character and check for palindrome:** The `if (IsPalindrome(s.Remove(i, 1)))` line inside the loop does two things:
   * `s.Remove(i, 1)` removes the character at index `i` from the string `s`. This creates a new string that is the same as `s` but without the character at index `i`.
   * `IsPalindrome(...)` checks if the resulting string is a palindrome. This is done by calling the `IsPalindrome` function, which is not shown in the provided code but is assumed to check if a string is a palindrome.
4. **Return true if a palindrome is found:** If the `IsPalindrome` function returns `true`, indicating that the string is a palindrome after removing the character at index `i`, the `ValidPalindrome` function immediately returns `true`.
5. **Return false if no palindrome is found:** If the loop has iterated over all characters in the string `s` and hasn't found a palindrome, the `ValidPalindrome` function returns `false`.

```csharp
public class Solution
{
    public bool ValidPalindrome(string s)
    {
        for (int i = 0; i < s.Length; i++)
        {
            if (IsPalindrome(s.Remove(i, 1)))
            {
                return true;
            }
        }
        return false;
    }

    public bool IsPalindrome(string s)
    {
        int i = 0, j = s.Length - 1;
        while (i < j)
        {
            if (s[i++] != s[j--])
            {
                return false;
            }
        }
        return true;
    }

}
```

> Complexity

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

#### Approach - Two pointers Technique

In this problem is that I will use two pointers so that we can check if the string is palindrome after excluding one of the chars.

**Steps**

1. **Initialize two pointers:** The `int left = 0, right = s.Length - 1;` line initializes two pointers, `left` and `right`. `left` starts at the beginning of the string `s` and `right` starts at the end.
2. **Start of the loop:** The `while (left < right)` line starts a loop that continues as long as `left` is less than `right`. This means the loop will continue until the two pointers meet or cross each other.
3. **Compare characters at the pointers:** The `if (s[left] == s[right])` line inside the loop compares the characters at the `left` and `right` positions. If they are the same, it increments `left` and decrements `right`, moving the pointers towards each other.
4. **Check for palindrome after removing a character:** If the characters at the `left` and `right` positions are not the same, the `else` block is executed. This block returns the result of `IsPalindrome(s, left + 1, right) || IsPalindrome(s, left, right - 1)`. This line checks if the string `s` would be a palindrome if either the character at the `left` position or the character at the `right` position were removed. It does this by calling the `IsPalindrome` function, which is not shown in the provided code but is assumed to check if a string is a palindrome.
5. **Return true if no mismatches are found:** If the loop has checked all pairs of characters and hasn't found any mismatches, the function returns `true`, indicating the string is a palindrome.

```csharp
public class Solution {
    public bool ValidPalindrome(string s) {
        int left = 0, right = s.Length - 1;

        while (left < right){
            if (s[left] == s[right]){
                left++;
                right--;
            }
            else 
            {
                // wost case 2N times execute left || right case.
                return IsPalindrome(s, left + 1, right) || IsPalindrome(s, left, right - 1);   
            }  
        }

        return true;
    }
    private bool IsPalindrome(string s, int left, int right){
        while (left < right){
            if (s[left] != s[right])
                return false;
            left++;
            right--;
        }
        return true;
    }
}
```

> Complexity

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