Valid Palindrome

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.

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: false Explanation: “raceacar” is not a palindrome.

Example 3:

Input: s = ” ” Output: true Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters.

Approach: Two Pointers (Optimal Solution)

Algorithm

1. Use two pointers, one at the start (left) and one at the end (right)
2. Skip non-alphanumeric characters from both ends
3. Convert each character to lowercase before comparing
4. If the characters differ, return false
5. Move both pointers inward and continue until they meet

Key Insight

Instead of first cleaning the string, we can compare characters in-place while skipping invalid ones. This avoids creating a new string and uses O(1) extra space.

Time & Space Complexity

• Time Complexity: O(n) - each character is processed at most once
• Space Complexity: O(1) - no extra data structures used

Java Implementation

public class ValidPalindrome {

    /**
     * Determine if a string is a valid palindrome.
     * A phrase is a palindrome if, after converting all uppercase letters into
     * lowercase and removing all non-alphanumeric characters, it reads the same
     * forward and backward.
     * @param s Input string
     * @return true if the string is a valid palindrome, false otherwise
     */
    public static boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            // Skip non-alphanumeric characters from the left
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            // Skip non-alphanumeric characters from the right
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }

            // Compare characters (case-insensitive)
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        System.out.println("Input: s = \"A man, a plan, a canal: Panama\"");
        System.out.println("Output: " + isPalindrome("A man, a plan, a canal: Panama")); // Expected: true

        // Test case 2
        System.out.println("Input: s = \"race a car\"");
        System.out.println("Output: " + isPalindrome("race a car")); // Expected: false

        // Test case 3
        System.out.println("Input: s = \" \"");
        System.out.println("Output: " + isPalindrome(" ")); // Expected: true
    }
}

Example Walkthrough

For s = "A man, a plan, a canal: Panama":

1. left=0 (‘A’), right=29 (‘a’): both alphanumeric. ‘a’ == ‘a’, move inward
2. left=1 (’ ’), skipped → left=2 (‘m’), right=28 (‘m’): ‘m’ == ‘m’, move inward
3. left=3 (‘a’), right=27 (‘a’): ‘a’ == ‘a’, move inward
4. left=4 (‘n’), right=26 (‘n’): ‘n’ == ‘n’, move inward
5. left=5 (’,’), skipped → left=6 (‘a’), right=25 (‘a’): ‘a’ == ‘a’, move inward

This continues until all pairs match, and the pointers meet. Return true.

For s = "race a car":

1. left=0 (‘r’), right=9 (‘r’): ‘r’ == ‘r’, move inward
2. left=1 (‘a’), right=8 (‘a’): ‘a’ == ‘a’, move inward
3. left=2 (‘c’), right=7 (‘c’): ‘c’ == ‘c’, move inward
4. left=3 (‘e’), right=6 (‘a’): ‘e’ != ‘a’. Return false

Alternative Approach with Cleaned String

public static boolean isPalindromeClean(String s) {
    StringBuilder cleaned = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (Character.isLetterOrDigit(c)) {
            cleaned.append(Character.toLowerCase(c));
        }
    }

    String str = cleaned.toString();
    int left = 0;
    int right = str.length() - 1;
    while (left < right) {
        if (str.charAt(left) != str.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

This approach first builds a cleaned string then compares, using O(n) extra space.

Key Insights

1. In-Place Comparison: Skips non-alphanumeric characters without building a new string
2. Case Insensitivity: Uses Character.toLowerCase() for case-insensitive comparison
3. Two Pointers: Compares characters from both ends moving toward the center
4. Edge Cases: Handles empty or whitespace-only strings correctly

The two-pointer approach is the optimal solution for this problem, providing linear time complexity with constant space.