Valid Palindrome II

String, Two Pointers

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.

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.

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)