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: Clean the input string s by removing non-alphanumeric characters and converting it to lowercase. This ensures that we only compare alphanumeric characters and ignore case sensitivity.
2. Two Pointers: Use two pointers, left and right, initialized to the beginning and end of the cleaned string, respectively.
3. Comparison: Compare the characters at left and right. If they are different, the string is not a palindrome; return false.
4. Iteration: Move the left pointer one step to the right and the right pointer one step to the left. Repeat step 3 until the left and right pointers cross each other.
5. Palindrome: If the loop completes without finding any mismatched characters, the string is a palindrome; return true.

Explanation:

The solution uses a two-pointer approach for efficient palindrome checking. By preprocessing the string, we simplify the comparison process by focusing only on relevant characters. The two pointers move towards the middle of the string, allowing for a linear time complexity solution.

Code:

using System;
using System.Text.RegularExpressions;

public class Solution {
    public bool IsPalindrome(string s) {
        // Preprocessing: Remove non-alphanumeric characters and convert to lowercase
        string cleanString = Regex.Replace(s.ToLower(), "[^a-z0-9]", "");

        // Two pointers
        int left = 0;
        int right = cleanString.Length - 1;

        // Comparison and Iteration
        while (left < right) {
            if (cleanString[left] != cleanString[right]) {
                return false; // Not a palindrome
            }
            left++;
            right--;
        }

        return true; // It's a palindrome
    }
}

Complexity:

• Time Complexity: O(n), where n is the length of the string. This is because we iterate through the cleaned string at most once. The Regex.Replace operation also has a linear time complexity in the average case.
• Space Complexity: O(n) in the worst case, primarily due to the creation of the cleanString. In the best case, if the input string is already clean, the space complexity is O(1). However, for most scenarios, the space used by cleanString is the dominating factor.