Valid Palindrome

String, Two Pointers

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.

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 ith 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 jth 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 ith and jth 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.

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)

PreviousLongest Substring Without Repeating CharactersNextValid Palindrome II

Last updated