Valid Palindrome

Ignore punctuation and case, then decide whether the string reads the same forward and backward.

Open concept page Back to problem map

This is a classic interview prompt for opposite-end pointers on strings.

It reinforces how to skip irrelevant characters without building extra data structures.

Problem intuition

The naive route is to clean the string and compare it with its reverse.

The more memory-efficient version keeps two pointers at the ends and skips every character that does not matter.

Java solution ladder

The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.

Solution 1

Normalize and reverse

O(n)O(n)

Build a cleaned lowercase string first, then compare it with its reverse. Clear idea, but it spends extra memory.

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder cleaned = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                cleaned.append(Character.toLowerCase(ch));
            }
        }

        String normalized = cleaned.toString();
        String reversed = cleaned.reverse().toString();
        return normalized.equals(reversed);
    }
}

Solution 2

Two pointers in place

O(n)O(1)

Walk from both ends, skipping non-alphanumeric characters and comparing meaningful characters only.

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int 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--;
            }

            char leftChar = Character.toLowerCase(s.charAt(left));
            char rightChar = Character.toLowerCase(s.charAt(right));

            if (leftChar != rightChar) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}