22. Valid Palindrome

🔗 LeetCode Problem: 125. Valid Palindrome
📊 Difficulty: Easy
🏷️ Topics: Two Pointers, String

Problem Statement

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 * 10^5 - s consists only of printable ASCII characters

🎨 Visual Understanding

The Problem Visualized

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

Step 1: Convert to lowercase
"a man, a plan, a canal: panama"

Step 2: Remove non-alphanumeric characters
"amanaplanacanalpanama"

Step 3: Check if palindrome
Read forward:  a m a n a p l a n a c a n a l p a n a m a
Read backward: a m a n a p l a n a c a n a l p a n a m a
               ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
Same! → Palindrome ✓

What is a Palindrome?

Palindrome: Reads the same forwards and backwards

Examples:
"racecar" → r a c e c a r
            ← same →
            Palindrome ✓

"hello" → h e l l o
          ≠ o l l e h
          Not palindrome ✗

"noon" → n o o n
         ← same →
         Palindrome ✓

Two Pointer Approach

String: "amanaplanacanalpanama"

Start with two pointers:
Left at beginning, Right at end

a m a n a p l a n a c a n a l p a n a m a
↑                                       ↑
left                                  right

Compare and move inward:
a m a n a p l a n a c a n a l p a n a m a
↑                                       ↑
'a' == 'a' ✓ Move both pointers

  m a n a p l a n a c a n a l p a n a m
  ↑                                   ↑
  'm' == 'm' ✓ Continue...

Keep comparing until pointers meet or cross

🎯 Approach 1: Clean String First

The Most Natural Thinking 💭

Core Logic:

Create a cleaned version of the string first:

1. Remove all non-alphanumeric characters
2. Convert to lowercase
3. Check if cleaned string is palindrome using two pointers

Why This Works: - Preprocessing simplifies the problem - Clear separation of concerns - Easy to understand and debug

Why This is Not Optimal: - Creates extra string (O(n) space) - Two passes through data - Can be optimized to single pass

Implementation

public boolean isPalindrome(String s) {
    // Step 1: Clean the string
    StringBuilder cleaned = new StringBuilder();

    for (char c : s.toCharArray()) {
        if (Character.isLetterOrDigit(c)) {
            cleaned.append(Character.toLowerCase(c));
        }
    }

    // Step 2: Check if palindrome using two pointers
    String cleanStr = cleaned.toString();
    int left = 0;
    int right = cleanStr.length() - 1;

    while (left < right) {
        if (cleanStr.charAt(left) != cleanStr.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }

    return true;
}

Step-by-Step Execution: s = "A man, a plan, a canal: Panama"

Step 1: Clean the string
═══════════════════════════════════════════════════════════════════
Input: "A man, a plan, a canal: Panama"

Process each character:
'A' → letter → add 'a'
' ' → not alphanumeric → skip
'm' → letter → add 'm'
'a' → letter → add 'a'
'n' → letter → add 'n'
',' → not alphanumeric → skip
' ' → not alphanumeric → skip
... (continue)

Cleaned: "amanaplanacanalpanama"


Step 2: Check palindrome with two pointers
═══════════════════════════════════════════════════════════════════
left=0, right=20
'a' == 'a' ✓

left=1, right=19
'm' == 'm' ✓

left=2, right=18
'a' == 'a' ✓

... (continue comparing)

All characters match!

═══════════════════════════════════════════════════════════════════
🎯 RESULT: true
═══════════════════════════════════════════════════════════════════

⏰ Time: O(n) - two passes
💾 Space: O(n) - cleaned string

✅ Approach 2: Two Pointers Without Extra Space (Optimal)

The Breakthrough Insight 💡

Core Logic:

Skip invalid characters on-the-fly:

1. Use two pointers on original string
2. Skip non-alphanumeric from both ends
3. Compare valid characters (case-insensitive)
4. Move pointers inward

No need to create cleaned string!

Why This is Better: - O(1) space - no extra string - Single pass through string - More efficient - Optimal solution!

Implementation

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

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

        // Skip non-alphanumeric from 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;
}

Step-by-Step Execution: s = "A man, a plan, a canal: Panama"

Initial State:
═══════════════════════════════════════════════════════════════════
s = "A man, a plan, a canal: Panama"
left = 0, right = 30


Iteration 1:
═══════════════════════════════════════════════════════════════════
s[0] = 'A' → alphanumeric ✓
s[30] = 'a' → alphanumeric ✓

Compare: toLowerCase('A') vs toLowerCase('a')
         'a' == 'a' ✓

left = 1, right = 29


Iteration 2:
═══════════════════════════════════════════════════════════════════
s[1] = ' ' → not alphanumeric, skip
left++ → left = 2

s[2] = 'm' → alphanumeric ✓
s[29] = 'm' → alphanumeric ✓

Compare: 'm' == 'm' ✓

left = 3, right = 28


Iteration 3:
═══════════════════════════════════════════════════════════════════
s[3] = 'a' → alphanumeric ✓
s[28] = 'a' → alphanumeric ✓

Compare: 'a' == 'a' ✓

left = 4, right = 27


Iteration 4:
═══════════════════════════════════════════════════════════════════
s[4] = 'n' → alphanumeric ✓
s[27] = 'n' → alphanumeric ✓

Compare: 'n' == 'n' ✓

left = 5, right = 26


Iteration 5:
═══════════════════════════════════════════════════════════════════
s[5] = ',' → not alphanumeric, skip
left++ → left = 6

s[6] = ' ' → not alphanumeric, skip
left++ → left = 7

s[7] = 'a' → alphanumeric ✓
s[26] = 'a' → alphanumeric ✓

Compare: 'a' == 'a' ✓

left = 8, right = 25

... (continue until pointers meet)


Final:
═══════════════════════════════════════════════════════════════════
left >= right → All characters matched

🎯 RESULT: true
═══════════════════════════════════════════════════════════════════

Another Example: s = "race a car"

Initial: left = 0, right = 9

s[0]='r', s[9]='r' → 'r'=='r' ✓, left=1, right=8
s[1]='a', s[8]='a' → 'a'=='a' ✓, left=2, right=7
s[2]='c', s[7]='c' → 'c'=='c' ✓, left=3, right=6
s[3]='e', s[6]=' ' → skip s[6], right=5
s[3]='e', s[5]='a' → 'e'!='a' ✗

Return false

Example: Empty after cleanup: s = " "

Initial: left = 0, right = 0

s[0] = ' ' → not alphanumeric
Skip from left: left++ → left=1

left >= right → Exit loop

Return true (empty string is palindrome)

⏰ Time: O(n) - single pass
💾 Space: O(1) - only two pointers

🎯 Approach 3: Using Regular Expression (Alternative)

Thought Process 💭

Core Logic:

Use regex to clean string, then check palindrome:

1. Use replaceAll to remove non-alphanumeric
2. Convert to lowercase
3. Compare with reverse

Why Mention This: - Concise one-liner approach - Good for languages with strong regex support - Easy to write and read

Not Recommended for Interview: - Less efficient than two pointers - O(n) extra space for cleaned string - Harder to explain time complexity

Implementation

public boolean isPalindrome(String s) {
    // Clean: remove non-alphanumeric and lowercase
    String cleaned = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();

    // Compare with reverse
    String reversed = new StringBuilder(cleaned).reverse().toString();

    return cleaned.equals(reversed);
}

⏰ Time: O(n)
💾 Space: O(n) - cleaned and reversed strings

🔍 Edge Cases

Case 1: Empty string
Input: s = ""
Output: true
Strategy: Empty is palindrome

Case 2: Single character
Input: s = "a"
Output: true

Case 3: Only non-alphanumeric
Input: s = ".,;"
Output: true
Explanation: Empty after cleanup

Case 4: Only spaces
Input: s = "   "
Output: true

Case 5: Mixed case palindrome
Input: s = "RaceCar"
Output: true
Explanation: "racecar" is palindrome

Case 6: Numbers included
Input: s = "A1b2B1a"
Output: true
Explanation: "a1b2b1a" is palindrome

Case 7: Two characters same
Input: s = "aa"
Output: true

Case 8: Two characters different
Input: s = "ab"
Output: false

Case 9: Special characters only at ends
Input: s = ".a."
Output: true
Explanation: "a" is palindrome

Common Mistakes

Mistake 1: Not handling case-insensitive comparison
❌ Wrong: if (s.charAt(left) != s.charAt(right))
✓ Right: if (Character.toLowerCase(s.charAt(left)) != 
             Character.toLowerCase(s.charAt(right)))

Mistake 2: Not skipping non-alphanumeric characters
❌ Wrong: Compare all characters including spaces/punctuation
✓ Right: Skip with Character.isLetterOrDigit()

Mistake 3: Wrong loop condition
❌ Wrong: while (left <= right)
✓ Right: while (left < right)
Reason: Equal means same character, no need to compare

Mistake 4: Not moving pointers after skipping
❌ Wrong: 
    if (!Character.isLetterOrDigit(s.charAt(left))) {
        // forgot left++
    }
✓ Right: Use while loop to skip all invalid chars

Mistake 5: Index out of bounds
❌ Wrong: Not checking left < right in skip loops
✓ Right: while (left < right && !isValid(...))

Mistake 6: Using equals() on char
❌ Wrong: s.charAt(left).equals(s.charAt(right))
✓ Right: s.charAt(left) == s.charAt(right)

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Clean String First
  Time: O(n)
  Space: O(n)
  Use: Clear but not optimal

Approach 2: Two Pointers In-Place (OPTIMAL)
  Time: O(n)
  Space: O(1)
  Use: Best for interviews

Approach 3: Regex + Reverse
  Time: O(n)
  Space: O(n)
  Use: Concise but less efficient

🔑 The Core Insight

Problem: Check if string is palindrome (ignore case and non-alphanumeric)

Key insight: Use two pointers from both ends
→ Skip non-alphanumeric characters on-the-fly
→ Compare characters case-insensitively
→ Move pointers toward center

Optimization: Don't create cleaned string
→ Skip invalid chars during comparison
→ Saves O(n) space
→ Still O(n) time with single pass

🎯 Pattern Recognition

Problem Type: String Validation with Two Pointers
Core Pattern: Two Pointers (Opposite Ends)

When to Apply:
✓ Need to compare from both ends
✓ Palindrome checking
✓ String validation/comparison
✓ Can skip certain characters

Key Techniques:
→ Two pointers moving toward center
→ Skip invalid characters with while loops
→ Case-insensitive comparison
→ Character utility methods (isLetterOrDigit, toLowerCase)

Related Problems:
- Valid Palindrome II (LC 680)
- Longest Palindromic Substring (LC 5)
- Palindrome Number (LC 9)
- Reverse String (LC 344)

🧠 Interview Strategy

Step 1: "Need to check if string is palindrome"
Step 2: "Ignore case and non-alphanumeric characters"
Step 3: "Could clean string first - O(n) space"
Step 4: "Better: two pointers, skip invalid chars on-the-fly"
Step 5: "O(n) time, O(1) space - optimal solution"

📝 Quick Revision Notes

🎯 Core Concept:

Use two pointers from opposite ends. Skip non-alphanumeric characters. Compare case-insensitively. Move toward center until pointers meet.

⚡ Quick Implementation:

public boolean isPalindrome(String s) {
    int i = 0;
    int j = s.length() - 1;

    while (i < j) {
        char ch1 = Character.toLowerCase(s.charAt(i));
        char ch2 = Character.toLowerCase(s.charAt(j));
        if(!isValid(ch1)) {
            i++;

            continue;
        }

        if(!isValid(ch2)) {
            j--;

            continue;
        }

        if(ch1 != ch2) {
            return false;
        } else {
            i++;
            j--;
        }
    }

    return true;
}

private boolean isValid(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
}

🔑 Key Insights:

Two pointers: start from opposite ends
Skip non-alphanumeric: Character.isLetterOrDigit()
Case-insensitive: Character.toLowerCase()
Loop condition: left < right (not <=)
Skip loops: check left < right to prevent out of bounds
Empty after cleanup: considered palindrome (return true)
O(1) space: no extra string needed
Single pass: O(n) time complexity

🎪 Memory Aid:

"Two ends meet in middle, skip junk, compare lowercase!"
Think: "Outside-in pointers, skip & compare"

Valid Palindrome II (LC 680)
Longest Palindromic Substring (LC 5)
Palindrome Number (LC 9)
Reverse String (LC 344)

Happy practicing! 🎯

22. Valid Palindrome

Problem Statement

🎨 Visual Understanding

The Problem Visualized

What is a Palindrome?

Two Pointer Approach

🎯 Approach 1: Clean String First

The Most Natural Thinking 💭

Implementation

Step-by-Step Execution: s = "A man, a plan, a canal: Panama"

✅ Approach 2: Two Pointers Without Extra Space (Optimal)

The Breakthrough Insight 💡

Implementation

Step-by-Step Execution: s = "A man, a plan, a canal: Panama"

Another Example: s = "race a car"

Example: Empty after cleanup: s = " "

🎯 Approach 3: Using Regular Expression (Alternative)

Thought Process 💭

Implementation

🔍 Edge Cases

Common Mistakes

🎯 Key Takeaways

⚡ Algorithm Comparison

🔑 The Core Insight

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

Related Patterns