Valid Palindrome easy

Problem Statement

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

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: Create a new string containing only alphanumeric characters from the input string, converting all characters to lowercase.
2. Two Pointers: Use two pointers, one at the beginning and one at the end of the processed string.
3. Comparison: Compare the characters at both pointers. If they are different, the string is not a palindrome.
4. Iteration: Move the left pointer one step to the right and the right pointer one step to the left, repeating step 3 until the pointers cross each other.
5. Result: If the loop completes without finding any different characters, the string is a palindrome.

Explanation:

The solution efficiently handles non-alphanumeric characters and case sensitivity by first cleaning the input string. The two-pointer approach provides a linear time solution, avoiding nested loops. The pointers move inwards, comparing characters from both ends simultaneously. This approach is optimized for speed and clarity.

Code:

function isPalindrome(s: string): boolean {
    // 1. Preprocessing: Create a new string with only alphanumeric characters in lowercase
    let processedString = s.toLowerCase().replace(/[^a-z0-9]/g, "");

    // 2. Two Pointers: Initialize pointers
    let left = 0;
    let right = processedString.length - 1;

    // 3 & 4. Comparison and Iteration:
    while (left < right) {
        if (processedString[left] !== processedString[right]) {
            return false; // Not a palindrome
        }
        left++;
        right--;
    }

    // 5. Result:  If the loop completes, it's a palindrome.
    return true;
}

Complexity:

• Time Complexity: O(n), where n is the length of the input string. This is because we iterate through the processed string once. The preprocessing step using regex also has a linear time complexity in the worst case.

• Space Complexity: O(n) in the worst case. This is because we create a new string processedString which could potentially be as long as the input string. In the best case (no non-alphanumeric characters), the space complexity could be O(1) if the string is modified in place (though this would make the code less readable). The space used by the pointers left and right is constant, O(1).