Crack the Backend

Problem Statement

Given a string s, return true if it is a palindrome after converting all uppercase letters to lowercase and removing all non-alphanumeric characters. A phrase is a palindrome if it reads the same forward and backward. Only alphanumeric characters (letters and numbers) are considered.

Ignore spaces, punctuation, and other non-alphanumeric characters. Compare only letters and digits, case-insensitive.
Empty string (after removal) is considered a palindrome.

Key Observations

Two pointers: one at the start and one at the end. Move both inward, skipping any character that is not alphanumeric. When both point to alphanumeric characters, compare them (using the same case, e.g. lowercase). If they differ, return false. If we meet in the middle without a mismatch, return true.
We need a helper to check "is alphanumeric" and to normalize (e.g. Character.toLowerCase) for comparison.

Approach

High-level: left = 0, right = s.length()-1. While left < right: skip non-alphanumeric from both sides. Compare Character.toLowerCase(s.charAt(left)) and Character.toLowerCase(s.charAt(right)); if not equal return false. Then left++, right--. Return true.

Steps:

While left < right: while left < right and !Character.isLetterOrDigit(s.charAt(left)), left++; while left < right and !Character.isLetterOrDigit(s.charAt(right)), right--.
If left < right and Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)), return false. left++, right--.
Return true.

Implementation

Java

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;

    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
            left++;
        }

        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
            right--;
        }

        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;
        }

        left++; right--;
    }

    return true;
}

Test Cases

Example 1

Input

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

Expected

true

Explanation

amanaplanacanalpanama is palindrome.

Complexity Analysis

Time: O(n).
Space: O(1).

Follow-ups

Check if a linked list is palindrome (O(1) space: find mid, reverse second half, compare).