Test1

test

•Easy

53w5

title: "Valid Palindrome" description: "Master the Two Pointer pattern with a clean, interview-ready solution." pattern: "Two Pointers" difficulty: "Easy" leetcode: 125 time: "O(n)" space: "O(1)"

🧠 Valid Palindrome

Pattern: Two Pointers
Difficulty: Easy
LeetCode: 125
Time: O(n) · Space: O(1)

🎯 Question 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 (a-z, A-Z) and numbers (0-9).

Given a string s, return true if it is a palindrome, or false otherwise.

Examples

| Input | Output | Explanation | |---|:---:|---| | "A man, a plan, a canal: Panama" | 🟢 true | Ignoring spaces and punctuation → amanaplanacanalpanama | | "race a car" | 🔴 false | Characters don't match from both ends | | " " | 🟢 true | No alphanumeric characters remain |

Constraints

1 <= s.length <= 2 * 10⁵
s consists only of printable ASCII characters.

💡 How to Explain It in an Interview

If the interviewer asks:

"How would you solve this?"

You can say:

"I would use the Two Pointer pattern. One pointer starts from the left and another starts from the right. I skip any non-alphanumeric characters, compare the two valid characters case-insensitively, and then move both pointers toward the center. If any pair doesn't match, I immediately return false. If all pairs match, the string is a palindrome."

🚀 Why Two Pointers?

We don't need to create another cleaned string.

Instead, we compare characters directly from the original string.

text

A man, a plan, a canal: Panama
 
↑                                     ↑
L                               R
 
Skip invalid characters
 
 ↓                       ↓
 
 a                             a
 
 └────────── COMPARE ──────────┘

This gives us:

⚡ O(n) Time
💾 O(1) Extra Space

🔍 Step-by-Step Algorithm

01. Start from both ends

text

left  → 0
right → n - 1

02. Skip invalid characters

If the left character isn't alphanumeric:

text

left++

If the right character isn't alphanumeric:

text

right--

03. Compare valid characters

Compare both characters after converting them to lowercase.

text

lower(s[left]) == lower(s[right])

If they are different:

text

return false

04. Move both pointers

After a successful comparison:

text

left++
right--

05. Finish

If all characters match:

text

return true

🧪 Sample Test Case

Input

text

s = "0P"

Step 1 — Start

text

0 P
↑ ↑
L R

Both characters are alphanumeric.

Step 2 — Convert to lowercase

text

'0' != 'p'

Step 3 — Mismatch

text

🔴 return false

💻 Solutions

🟦 C++

cpp

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0;
        int right = s.length() - 1;
 
        while (left <= right) {
 
            if (!isalnum(s[left])) {
                left++;
            }
            else if (!isalnum(s[right])) {
                right--;
            }
            else {
                if (tolower(s[left]) != tolower(s[right])) {
                    return false;
                }
 
                left++;
                right--;
            }
        }
 
        return true;
    }
};

🟪 Java

java

class Solution {
    public boolean isPalindrome(String s) {
        int start = 0;
        int last = s.length() - 1;
 
        while (start <= last) {
            char currFirst = s.charAt(start);
            char currLast = s.charAt(last);
 
            if (!Character.isLetterOrDigit(currFirst)) {
                start++;
            }
            else if (!Character.isLetterOrDigit(currLast)) {
                last--;
            }
            else {
                if (Character.toLowerCase(currFirst) !=
                    Character.toLowerCase(currLast)) {
                    return false;
                }
 
                start++;
                last--;
            }
        }
 
        return true;
    }
}

🟨 JavaScript

javascript

class Solution {
    isPalindrome(s) {
        let left = 0;
        let right = s.length - 1;
 
        const isAlphaNumeric = (ch) => {
            return /[a-zA-Z0-9]/.test(ch);
        };
 
        while (left <= right) {
            if (!isAlphaNumeric(s[left])) {
                left++;
            }
            else if (!isAlphaNumeric(s[right])) {
                right--;
            }
            else {
                if (
                    s[left].toLowerCase() !==
                    s[right].toLowerCase()
                ) {
                    return false;
                }
 
                left++;
                right--;
            }
        }
 
        return true;
    }
}

🐍 Python

python

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1
 
        while left <= right:
 
            if not s[left].isalnum():
                left += 1
 
            elif not s[right].isalnum():
                right -= 1
 
            else:
                if s[left].lower() != s[right].lower():
                    return False
 
                left += 1
                right -= 1
 
        return True

⏱️ Complexity Analysis

| Metric | Complexity | |---|:---:| | 🕐 Time | O(n) | | 💾 Extra Space | O(1) |

Why O(n)?

Both pointers move only toward the center.

Each character is processed at most a constant number of times.

Why O(1) Space?

We don't create another string or array.

Only two pointers and a few variables are used.

🧩 Pattern to Remember

text

            TWO POINTERS
                  ↓
        Start from both ends
                  ↓
        Skip invalid characters
                  ↓
          Compare characters
                  ↓
        ┌─────────┴─────────┐
        ↓                   ↓
    Mismatch              Match
        ↓                   ↓
      false          Move inward
                            ↓
                     Pointers cross
                            ↓
                          true

⭐ Interview Takeaway

When a problem asks you to compare elements from opposite ends of a sequence, think Two Pointers.

The key idea is:

text

LEFT  → → →     ← ← ←  RIGHT

Move inward until the pointers meet or a mismatch is found.