Valid Palindrome

Author: Nikhitha
Category: C++ | Problem Solving | LeetCode
Topic: String Manipulation + Two Pointer Technique

🔍 Problem Statement

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

✅ Example Inputs & Outputs

💡 What Is a Palindrome?

A palindrome is a word or sentence that reads the same forwards and backwards, ignoring punctuation, spaces, and letter casing.

🧪 Solution 1: Brute Force (Clean, Reversed Comparison)

✔️ Intuition:

1. Filter the input string to remove all non-alphanumeric characters.

2. Convert everything to lowercase for case-insensitive comparison.

3. Reverse the filtered string.

4. If the original filtered string equals the reversed one → it’s a palindrome!

🔗 Code:

class Solution {
public:
    bool isPalindrome(string s) {
        int n = s.size();
        if(s == "")
            return true;

        string result = "";
        for (int i = 0; i < n; i++) {
            if (isalnum(s[i]))
                result += tolower(s[i]);
        }

        string reversal = result;
        reverse(reversal.begin(), reversal.end());

        return result == reversal;
    }
};

⏱️ Time & Space Complexity:

• Time: O(n)

• Space: O(n) → for the result and reversal strings.

⚙️ Key Functions Used:

• isalnum(c) – checks if character c is a letter or digit.

• tolower(c) – converts character c to lowercase.

• reverse(str.begin(), str.end()) – reverses the string.

🚀 Solution 2: Optimized – Two Pointer Technique

✔️ Intuition:

Let’s be memory-smart! Why create new strings when we can just compare characters from both ends?

• Use two pointers: left at start, right at end.

• Skip non-alphanumeric characters.

• Convert both chars to lowercase and compare.

• If all pairs match → it’s a palindrome.

🔗 Code:

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

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

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

            left++;
            right--;
        }

        return true;
    }
};

🧠 Key Concepts:

⏱️ Time & Space Complexity:

• Time: O(n)

• Space: O(1) → no extra strings, pure pointer logic!

📌 Final Thoughts

If you're prepping for coding interviews or placements, go with the two pointer version — it's clean, memory-efficient, and shows you understand core algorithmic patterns.

🧪 Test Cases to Try

Solution sol;
cout << sol.isPalindrome("race a car") << endl; // false
cout << sol.isPalindrome(" ") << endl;          // true
cout << sol.isPalindrome("0P") << endl;         // false
cout << sol.isPalindrome("madam") << endl;      // true

problem link: https://leetcode.com/problems/valid-palindrome/description/