Palindrome Checker

Problem Statement

Write a Java program that implements a method to check if a string is a palindrome, ignoring case and non-alphanumeric characters (e.g., spaces, punctuation). A palindrome is a string that reads the same forward and backward. The program should return a boolean indicating whether the input is a palindrome and test the implementation with various inputs, including empty strings, single characters, and strings with special characters. You can visualize this as checking if a phrase, like a secret code, reads the same when flipped, after ignoring irrelevant symbols and letter case, as if decoding a message on a mirror.

Input: A string (e.g., "A man, a plan, a canal: Panama", "race a car", ""). Output: A boolean (true if the string is a palindrome after ignoring case and non-alphanumeric characters, false otherwise). Constraints:

• String length is between 0 and 10^5.
• The string may contain any ASCII characters (letters, digits, spaces, punctuation).
• The input may be empty or null. Example:
• Input: "A man, a plan, a canal: Panama"
• Output: true
• Explanation: After ignoring case and non-alphanumeric characters, the string becomes "amanaplanacanalpanama", which is a palindrome.
• Input: "race a car"
• Output: false
• Explanation: After cleaning, the string becomes "raceacar", which is not a palindrome.
• Input: ""
• Output: true
• Explanation: An empty string is considered a palindrome.

Pseudocode

FUNCTION isPalindrome(input)
    IF input is null THEN
        RETURN false
    ENDIF
    SET cleaned to empty string
    FOR each character c in input
        IF c is alphanumeric THEN
            SET cleaned to cleaned + lowercase(c)
        ENDIF
    ENDFOR
    SET left to 0
    SET right to length of cleaned - 1
    WHILE left < right
        IF cleaned[left] not equal to cleaned[right] THEN
            RETURN false
        ENDIF
        INCREMENT left
        DECREMENT right
    ENDWHILE
    RETURN true
ENDFUNCTION

FUNCTION main()
    SET testStrings to array of strings including various cases
    FOR each string in testStrings
        PRINT input string
        CALL isPalindrome(string)
        PRINT result
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Check if the input string is null; if so, return false.
2. Create a cleaned string by: a. Converting the input to lowercase. b. Including only alphanumeric characters (letters and digits).
3. Use two pointers (left and right) to check if the cleaned string is a palindrome: a. Start left at index 0 and right at the last index. b. While left < right, compare characters; if they differ, return false. c. Increment left and decrement right.
4. If the loop completes, return true (the string is a palindrome).
5. In the main method, test with various strings, including empty, single-character, and strings with special characters, printing the input and result.

Java Implementation

public class PalindromeChecker {
    // Checks if a string is a palindrome, ignoring case and non-alphanumeric characters
    public boolean isPalindrome(String input) {
        if (input == null) {
            return false;
        }
        // Clean the string: lowercase and keep only alphanumeric characters
        StringBuilder cleaned = new StringBuilder();
        for (char c : input.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                cleaned.append(Character.toLowerCase(c));
            }
        }
        // Check palindrome using two pointers
        int left = 0;
        int right = cleaned.length() - 1;
        while (left < right) {
            if (cleaned.charAt(left) != cleaned.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    // Main method to test isPalindrome with various inputs
    public static void main(String[] args) {
        PalindromeChecker checker = new PalindromeChecker();

        // Test cases
        String[] testStrings = {
            "A man, a plan, a canal: Panama", // Palindrome
            "race a car",                     // Not a palindrome
            "",                              // Empty string
            "A",                             // Single character
            "12321",                         // Numeric palindrome
            "Hello, World!",                 // Not a palindrome
            "RaCeCaR"                        // Palindrome (case-insensitive)
        };

        for (int i = 0; i < testStrings.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Input: \"" + testStrings[i] + "\"");
            boolean result = checker.isPalindrome(testStrings[i]);
            System.out.println("Is palindrome: " + result + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input: "A man, a plan, a canal: Panama"
Is palindrome: true

Test case 2:
Input: "race a car"
Is palindrome: false

Test case 3:
Input: ""
Is palindrome: true

Test case 4:
Input: "A"
Is palindrome: true

Test case 5:
Input: "12321"
Is palindrome: true

Test case 6:
Input: "Hello, World!"
Is palindrome: false

Test case 7:
Input: "RaCeCaR"
Is palindrome: true

Explanation:

• Test case 1: "A man, a plan, a canal: Panama" → "amanaplanacanalpanama", palindrome.
• Test case 2: "race a car" → "raceacar", not a palindrome.
• Test case 3: Empty string "" → "", palindrome.
• Test case 4: "A" → "a", palindrome.
• Test case 5: "12321" → "12321", palindrome.
• Test case 6: "Hello, World!" → "helloworld", not a palindrome.
• Test case 7: "RaCeCaR" → "racecar", palindrome.

How It Works

• Step 1: Check for null input; return false if null.
• Step 2: Clean the input using StringBuilder:
  • Iterate through each character.
  • If alphanumeric (using Character.isLetterOrDigit), append its lowercase version (Character.toLowerCase).
• Step 3: Use two pointers to check palindrome:
  • Compare characters at left and right; if different, return false.
  • Move left rightward and right leftward until they meet.
• Example Trace (Test case 1):
  • Input: "A man, a plan, a canal: Panama".
  • Cleaned: "amanaplanacanalpanama".
  • Check: left = 0 ('a') vs right = 19 ('a'), left = 1 ('m') vs right = 18 ('m'), etc., all match → true.
• Main Method: Tests with various inputs, including palindromes, non-palindromes, empty strings, and strings with special characters.
• Palindrome Property: Ignores case and non-alphanumeric characters, focusing only on letters and digits.

Complexity Analysis Table

Note:

• n is the length of the input string.
• Time complexity: O(n) for cleaning (iterating through the string) + O(n) for palindrome check (two-pointer traversal) = O(n).
• Space complexity: O(n) for the cleaned string in StringBuilder; palindrome check uses O(1) extra space.
• Best, average, and worst cases are O(n) time and O(n) space.

✅ Tip: Use Character.isLetterOrDigit and Character.toLowerCase to handle case and non-alphanumeric characters efficiently. Test with mixed cases, punctuation, and empty strings to ensure robustness.

⚠ Warning: Check for null input to avoid NullPointerException. Be aware that cleaning the string may significantly reduce its length if it contains many non-alphanumeric characters.