Valid Palindrome easy

Problem Statement

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

Example 1:

Input: "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama"

Example 2:

Input: "race a car" Output: true Explanation: "racecar"

Steps

1. Preprocessing: Clean the input string by removing non-alphanumeric characters and converting it to lowercase.
2. Two Pointers: Use two pointers, one at the beginning and one at the end of the cleaned string.
3. Comparison: Compare the characters at both pointers. If they are different, it's not a palindrome.
4. Iteration: Move the left pointer to the right and the right pointer to the left, repeating step 3 until the pointers cross.
5. Result: If all comparisons are successful, it's a palindrome; otherwise, it's not.

Explanation

The solution efficiently handles the constraints of the problem. The preprocessing step simplifies the comparison by eliminating irrelevant characters. The two-pointer approach provides a linear time solution, avoiding nested loops. The use of Character.isLetterOrDigit() ensures that only alphanumeric characters are considered, and Character.toLowerCase() handles case-insensitivity.

Code

class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true; //Empty string is a palindrome
        }

        //Preprocessing: remove non-alphanumeric characters and convert to lowercase
        String cleanString = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();

        int left = 0;
        int right = cleanString.length() - 1;

        //Two pointer comparison
        while (left < right) {
            if (cleanString.charAt(left) != cleanString.charAt(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 string at most once during preprocessing and once with the two-pointer approach. The replaceAll() method in Java has a time complexity of O(n) in the worst case.

• Space Complexity: O(n) in the worst-case scenario, although it could be O(1) if we modify the original string inplace, but we create a new string cleanString. The space used by left and right pointers is constant, O(1).