What is the brute force approach and complexity for Valid Palindrome?

Build the cleaned string and its reverse, then compare them with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Valid Palindrome?

Compare mirrored characters in place, skipping non-alphanumerics with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Valid Palindrome?

Look for key signals in the prompt: "reads the same forwards and backwards" indicates Position i must match its mirror position → compare from both ends at once.; "ignore non-alphanumeric characters" indicates Each pointer may need to skip forward on its own before a comparison.; "return true / false" indicates One mismatch ends it early. No need to build anything..

Valid Palindrome

Easy·LeetCode #125Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTwo Pointers (opposite ends)

Complexity:O(N)→O(N)

Key Insight

Put left at the start and right at the end. If either one is on a character that doesn't count, move it inward. Otherwise compare the two characters (ignoring case). If they differ, the answer is false. If they match, move both inward. When they meet, every pair has matched, so the answer is true.

Core Validity Invariant

The string is a palindrome only if every mirrored pair of real characters matches (ignoring case). So one mismatch anywhere means false, and running out of pairs means true.

Problem

You are given a string s.

First, imagine cleaning it: turn every uppercase letter into lowercase, and throw away everything that is not a letter or a digit (spaces, commas, colons, and so on).

Return true if the cleaned string reads the same forwards and backwards (a palindrome), and false otherwise.

Input

A string s made of printable ASCII characters.

Output

true if s is a palindrome after cleaning, otherwise false.

Example 1

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

Output: true

After cleaning it becomes "amanaplanacanalpanama", which reads the same both ways.

Example 2

Input: s = "race a car"

Output: false

After cleaning it becomes "raceacar". Backwards that is "racaecar" — different.

Example 3

Input: s = " "

Output: true

After cleaning, nothing is left. An empty string reads the same both ways.

Constraints

• 1 ≤ s.length ≤ 2 · 10^5
• s contains only printable ASCII characters.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
What does "reads the same backwards" mean in terms of positions? Which character must match the first one?
2.
Do I really need to build the cleaned string, or can I just ignore the extra characters while reading?
3.
If I find one pair of characters that don't match, do I need to look at the rest?
4.
After I check the outermost pair, what problem is left?
5.
What should happen with a string that has no letters or digits at all?

Brute force approach

Idea

Do exactly what the statement says. Build a new string with only the letters and digits, in lowercase. Make a reversed copy of it. The answer is whether the two strings are equal.

Thinking process

1
The statement describes a cleaning step, so the first idea is to actually do it.
2
Walk through s and keep only letters and digits, lowercased.
3
"Reads the same backwards" is literally cleaned == reverse(cleaned).
4
Build the reversed copy and compare.

Visual

Correct, but it builds two extra strings as long as the input. The two-pointer version reads the original string in place.

Clean, reverse, compares = "race a car"step 1/15

␣

▲i

cleaned

Extra memory

cleaned: 1 chars

copy 'r'

'r' is a letter, so its lowercase form goes into the new string.

Code & Implementation

brute.cpp

class Solution {
public:
    bool isPalindrome(string s) {
        // 1. Build a cleaned copy: only letters and digits, all lowercase.
        string cleaned;
        for (char c : s) {
            if (isalnum((unsigned char)c)) {
                cleaned += (char)tolower((unsigned char)c);
            }
        }

        // 2. A palindrome reads the same backwards, so compare with its reverse.
        string reversed(cleaned.rbegin(), cleaned.rend());
        return cleaned == reversed;
    }
};

class Solution {
    public boolean isPalindrome(String s) {
        // 1. Build a cleaned copy: only letters and digits, all lowercase.
        StringBuilder cleaned = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                cleaned.append(Character.toLowerCase(c));
            }
        }

        // 2. A palindrome reads the same backwards, so compare with its reverse.
        String str = cleaned.toString();
        String reversed = new StringBuilder(cleaned).reverse().toString();
        return str.equals(reversed);
    }
}

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 1. Build a cleaned copy: only letters and digits, all lowercase.
        cleaned = [c.lower() for c in s if c.isalnum()]

        # 2. A palindrome reads the same backwards, so compare with its reverse.
        return cleaned == cleaned[::-1]

export function isPalindrome(s: string): boolean {
    // 1. Build a cleaned copy: only letters and digits, all lowercase.
    const cleaned: string[] = [];
    for (const c of s) {
        if (/[a-zA-Z0-9]/.test(c)) {
            cleaned.push(c.toLowerCase());
        }
    }

    // 2. A palindrome reads the same backwards, so compare with its reverse.
    const str = cleaned.join("");
    const reversed = [...cleaned].reverse().join("");
    return str === reversed;
}

Complexity

Time O(N)Space O(N)

The time is already fine. The cost is memory: two new strings, each as long as the input in the worst case. We can check the same thing with no extra strings at all.

Optimized approach

Idea

Start from brute force

Brute force builds cleaned and reversed, then compares them position by position: cleaned[0] with reversed[0], cleaned[1] with reversed[1], and so on.

Find the repeated work

reversed[i] is just cleaned[len − 1 − i]. So the comparison is really "first vs last, second vs second-last, …". The extra strings only hold characters that are already in s. We copied data just to read it in a different order.

Define the state — what variables do I need?

left: Index of the next character to check from the front.
right: Index of the next character to check from the back.
s[left … right]: The middle part we haven't checked yet. Everything outside it is already known to be fine (matched pairs or ignored characters).

Define validity

The string is a palindrome only if every mirrored pair of real characters matches (ignoring case). So one mismatch anywhere means false, and running out of pairs means true.

Define the transitions — when does each pointer move, and why is it safe?

s[left] is not a letter or digit

left++

That character is thrown away by the cleaning step. It has no partner to match, so skipping it changes nothing.

s[right] is not a letter or digit

right--

Same reason, from the other side.

Both are real characters and tolower(s[left]) != tolower(s[right])

return false

These two are mirror partners in the cleaned string. If they differ, the cleaned string is not the same backwards, no matter what the middle looks like.

Both are real characters and they match

left++, right--

This pair is done. What's left to check is exactly the smaller middle part, and it must be a palindrome on its own.

left >= right

return true

No pairs are left. A single middle character (or nothing) is always its own mirror.

What does the current window add to the answer?

Each matched pair proves one more layer of the palindrome from the outside in. Each skipped character is one the cleaning step would have removed anyway.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = (int)s.size() - 1;

        while (left < right) {
            // Skip characters that don't count (spaces, punctuation).
            if (!isalnum((unsigned char)s[left])) {
                left++;
            } else if (!isalnum((unsigned char)s[right])) {
                right--;
            } else {
                // Both sides point at real characters: they must match.
                if (tolower((unsigned char)s[left]) != tolower((unsigned char)s[right])) {
                    return false;   // one mismatch is enough to say "no"
                }
                left++;
                right--;
            }
        }
        return true;   // every pair matched
    }
};

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

        while (left < right) {
            // Skip characters that don't count (spaces, punctuation).
            if (!Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            } else if (!Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            } else {
                // Both sides point at real characters: they must match.
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false; // one mismatch is enough to say "no"
                }
                left++;
                right--;
            }
        }
        return true; // every pair matched
    }
}

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left < right:
            # Skip characters that don't count (spaces, punctuation).
            if not s[left].isalnum():
                left += 1
            elif not s[right].isalnum():
                right -= 1
            else:
                # Both sides point at real characters: they must match.
                if s[left].lower() != s[right].lower():
                    return False  # one mismatch is enough to say "no"
                left += 1
                right -= 1

        return True  # every pair matched

export function isPalindrome(s: string): boolean {
    let left = 0;
    let right = s.length - 1;

    const isAlphanumeric = (c: string): boolean => /[a-zA-Z0-9]/.test(c);

    while (left < right) {
        // Skip characters that don't count (spaces, punctuation).
        if (!isAlphanumeric(s[left])) {
            left++;
        } else if (!isAlphanumeric(s[right])) {
            right--;
        } else {
            // Both sides point at real characters: they must match.
            if (s[left].toLowerCase() !== s[right].toLowerCase()) {
                return false; // one mismatch is enough to say "no"
            }
            left++;
            right--;
        }
    }
    return true; // every pair matched
}

Complexity

Time O(N)Space O(1)

Each step moves left right or right left (or both), and they stop when they meet. So there are at most N steps, and only two integers of extra memory.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Build the cleaned string and its reverse, then compare them	O(N)	O(N)
Optimal	Compare mirrored characters in place, skipping non-alphanumerics	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“reads the same forwards and backwards”Position i must match its mirror position → compare from both ends at once.
“ignore non-alphanumeric characters”Each pointer may need to skip forward on its own before a comparison.
“return true / false”One mismatch ends it early. No need to build anything.

Symmetric structure+compare mirrored positions+skip what doesn't count→Two Pointers (opposite ends)

This is the anchor of the opposite-ends family: start at both ends, look at the pair, decide, move inward. Here the decision is the simplest possible — the two sides must simply be equal, and a match moves both pointers at once. The next questions keep the same "two ends move toward each other" shape but change the decision: in Two Sum II only one side moves, chosen by whether the sum is too big or too small.

Don't make this mistake

Pattern confusion: treating it as a sliding window

Both pointers here start at opposite ends and walk toward each other. There is no window that grows and shrinks, and nothing between the pointers is being summed or counted. If you write for (right = 0; ...) with left chasing it, you are comparing neighbours, not mirror partners. Palindrome = mirrored pairs = opposite ends.

Forgetting to ignore case

✗ if (s[left] != s[right]) return false;

✓ if (tolower(s[left]) != tolower(s[right])) return false;

"Aa" is a palindrome. Without tolower, 'A' and 'a' look different.

Skipping with a nested while that runs past the other pointer

✗ while (!isalnum(s[left])) left++;

✓ while (left < right && !isalnum(s[left])) left++;

For a string like ".," the inner loop keeps going past right (and even past the end of the string). Always keep the left < right check, or use the if / else-if form shown in the solution.

Thinking digits don't count

The rule is letters and digits. "0P" is not a palindrome: '0' and 'p' are both real characters and they differ. Use isalnum, not isalpha.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Two Pointers translate into production architectures and low-level memory mechanics.

LLD Architecture

Circular Buffer & Ring Queue

Two pointer read/write head synchronization in production memory pools.

Explore Track

C++ Internals

Pointers vs References Deep Dive

Pointer arithmetic, dereferencing semantics, and memory layout behind in-place array passes.

Explore Track

C++ Internals

const Correctness & East-Const

Passing read-only spans with const int* without copying buffers.

Explore Track

Two Sum II – Input Array Is Sorted