Valid Palindrome easy

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forwards 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: true Explanation: "raceacar" is a palindrome.

Steps:

1. Preprocessing: Convert the input string s to lowercase and remove all non-alphanumeric characters. We can achieve this using a list comprehension and isalnum() method.
2. Two-Pointer Approach: Use two pointers, one at the beginning and one at the end of the processed string.
3. Comparison: Compare the characters at the two pointers. If they are different, the string is not a palindrome, and we return False.
4. Iteration: Move the left pointer to the right and the right pointer to the left, continuing the comparison until the pointers cross each other.
5. Palindrome: If the loop completes without finding any differing characters, the string is a palindrome, and we return True.

Explanation:

The solution leverages the two-pointer technique for efficient palindrome checking. Preprocessing the string simplifies the comparison by ensuring we only deal with alphanumeric characters in lowercase. The two pointers effectively check for symmetry from both ends of the string simultaneously.

Code:

def isPalindrome(s: str) -> bool:
    """
    Checks if a given string is a palindrome after removing non-alphanumeric characters and converting to lowercase.
    """
    processed_s = ''.join(c.lower() for c in s if c.isalnum())  #Preprocessing step
    left = 0
    right = len(processed_s) - 1

    while left < right:
        if processed_s[left] != processed_s[right]:
            return False
        left += 1
        right -= 1

    return True

Complexity:

• Time Complexity: O(n), where n is the length of the string. This is because we iterate through the string once for preprocessing and then again (effectively) using the two-pointer approach.
• Space Complexity: O(n) in the worst case, although it's O(k) where k is the length of the processed string (which could be significantly smaller than n) to store the processed string. In the average case, the space complexity is O(k), which could be considered O(1) if we modify the function to avoid creating a new string during preprocessing. We could modify the algorithm to use only indices to refer to the original string, thus eliminating the creation of a new string.