125. Valid Palindrome#

Difficulty: Easy

Link to Problem: To see the Valid Palindrome problem on LeetCode, click here!

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.

Constraints:

  • 1 <= s.length <= \(2*10^5\)

  • s consists only of printable ASCII characters.

Solution:#

Here’s a Python function to solve this problem:

def isPalindrome(s):
    # Step 1: Convert the input string to lowercase
    s = s.lower()
    
    # Step 2: Remove all non-alphanumeric characters from the string
    cleaned_s = ''.join(c for c in s if c.isalnum())
    
    # Step 3: Initialize two pointers, one at the beginning and one at the end of the cleaned string
    left, right = 0, len(cleaned_s) - 1
    
    # Step 4: Compare characters using the two pointers while moving them towards each other
    while left < right:
        if cleaned_s[left] != cleaned_s[right]:
            return False  # If characters don't match, it's not a palindrome
        left += 1
        right -= 1
    
    # Step 5: If the loop completes without returning False, it's a palindrome
    return True

Explanation:#

  1. The isPalindrome function takes an input string s.

  2. It starts by converting the input string to lowercase using s.lower(). This step ensures that the function is case-insensitive when checking for palindromes.

  3. Next, it removes all non-alphanumeric characters from the string and stores the result in the cleaned_s variable. It does this by iterating through each character in the input string and only keeping characters that are alphanumeric (letters and digits). This step removes spaces, punctuation, and other non-alphanumeric characters.

  4. The function then initializes two pointers, left and right, which will be used to compare characters from the beginning and end of the cleaned string.

  5. In a while loop, it compares characters using the two pointers while moving them towards each other. The loop continues until the left pointer is less than the right pointer. This is done to check all characters in the cleaned string.

  6. Inside the loop, it checks if the characters at the left and right pointers don’t match. If they don’t match, it means the input is not a palindrome, so the function returns False.

  7. If the characters at the left and right pointers match, the pointers are moved closer to each other by incrementing left and decrementing right.

  8. The loop continues to compare characters until it either finds a mismatch (returning False) or until the left pointer is greater than or equal to the right pointer. If the loop completes without finding a mismatch, it means the input is a palindrome, so the function returns True.

In summary, the code converts the input string to lowercase, removes non-alphanumeric characters, and then uses two pointers to compare characters from the cleaned string’s beginning and end. If all characters match during the comparison, the function returns True, indicating that the input is a palindrome. If any characters do not match, it returns False.

Test cases#

# Example 1:
input1 = "A man, a plan, a canal: Panama"
output1 = isPalindrome(input1)
print(output1)

True

# Example 2
input2 = "race a car"
output2 = isPalindrome(input2)
print(output2)

False

# Example 3
input3 = ""
output3 = isPalindrome(input3)
print(output3)

True

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the isPalindrome function that uses two pointers:

  1. Time Complexity:

    • Converting the input string to lowercase using s.lower() takes O(n) time, where ‘n’ is the length of the input string.

    • Removing non-alphanumeric characters using the list comprehension ''.join(c for c in s if c.isalnum()) also takes O(n) time because it iterates through each character in the string once.

    • The comparison of characters using the two pointers (left and right) is done in a loop that runs until left is less than right. In the worst case, the loop iterates through half of the string, so it takes O(n/2) time, which is still considered O(n).

    Therefore, the overall time complexity of the isPalindrome function is O(n), where ‘n’ is the length of the input string.

  2. Space Complexity:

    • The space complexity is primarily determined by the additional string cleaned_s created to store the cleaned version of the input string. In the worst case, if all characters in the input string are alphanumeric, this cleaned string can be as large as the original input string.

    • Additionally, the function uses two pointers, left and right, which consume constant space and do not depend on the size of the input.

In summary, the overall space complexity of the isPalindrome function is O(n) in the worst case, where ‘n’ is the length of the input string. The space complexity is dominated by the space required for cleaned_s.

Challenging Exercises:#

  1. Longest Palindromic Substring: Given a string s, find and return the longest palindromic substring within s. For example, if s = "babad", the function should return "bab" or "aba".

  2. Palindrome with Limited Characters: Given a string s and a list of characters allowed_chars, check if s is a palindrome considering only the characters from allowed_chars. Ignore all other characters. For example, if s = "A man, a plan, a canal: Panama" and allowed_chars = ['a', 'm', 'n', 'p'], the function should return True.