LeetCode Solution: 125. Valid Palindrome

#leetcode #dsa #programming #tutorial

Is "A man, a plan, a canal: Panama" a Palindrome? Let's Find Out! 🕵️‍♀️

Hey fellow coders and aspiring problem-solvers! 👋 Vansh2710 here, ready to dive into another LeetCode adventure. Today, we're tackling a classic string manipulation problem: 125. Valid Palindrome. It sounds simple, right? But there are a few twists that make it a fantastic exercise for beginners!

📖 Problem Explanation: What's a Palindrome Anyway?

At its core, a palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward. Think "madam" or "racecar".

However, LeetCode's version adds a little challenge:

Case Insensitivity: We need to treat 'A' and 'a' as the same character. So, "Racecar" should be considered a palindrome.
Alphanumeric Only: We only care about letters (a-z, A-Z) and numbers (0-9). Punctuation, spaces, and symbols? Gone! 👋
The Goal: Given a string s, your task is to return true if it's a valid palindrome after these transformations, and false otherwise.

Let's look at the examples:

Example 1: s = "A man, a plan, a canal: Panama"
- After cleaning: "amanaplanacanalpanama"
- Is it a palindrome? True!
Example 2: s = "race a car"
- After cleaning: "raceacar"
- Is it a palindrome? False! (The first 'r' doesn't match the last 'r', but the 'e' doesn't match the 'c', etc.)
Example 3: s = " " (an empty string with a space)
- After cleaning: "" (an empty string)
- Is an empty string a palindrome? True! (It reads the same forward and backward because there's nothing to compare!)

🤔 Intuition: The "Aha!" Moment

When you first hear "palindrome," your brain probably goes straight to comparing characters from the beginning and end. Like checking if word[0] == word[last_index], then word[1] == word[last_index - 1], and so on. This is the two-pointer technique, and it's perfect for palindromes!

But wait, we have all those pesky spaces, commas, and different cases! Before we can apply our awesome two-pointer strategy, we need to pre-process the string. The "aha!" is realizing that we can't just jump into comparing characters. We first need to create a clean slate—a version of the string that only contains lowercase alphanumeric characters. Once we have that, checking for a palindrome becomes trivial!

🚀 Approach: Step-by-Step Cleaning and Checking

Our strategy will involve three main steps:

Filter Out Non-Alphanumeric Characters: We'll iterate through the original string s. For each character, we'll decide if it's a letter or a number. If it is, we'll keep it. If not, we'll toss it! We'll collect all the "keepers" into a new, temporary string.
Convert to Lowercase: Now that our temporary string only has alphanumeric characters, we need to make sure all letters are in lowercase. This ensures "Racecar" becomes "racecar" and can be correctly compared.
Two-Pointer Palindrome Check: With our perfectly clean, lowercase, alphanumeric string, we can finally use the classic two-pointer approach!
- Set one pointer (s_idx) at the beginning of the temp string.
- Set another pointer (e_idx) at the end of the temp string.
- While s_idx is less than or equal to e_idx:
  - Compare the characters at temp[s_idx] and temp[e_idx].
  - If they are not equal, then the string is not a palindrome. Return false immediately!
  - If they are equal, move s_idx one step forward and e_idx one step backward.
- If the loop finishes without finding any mismatches, it means our string is a palindrome! Return true.

This structured approach makes a complex-sounding problem very manageable!

💻 Code: Bringing It to Life (C++)

Here's the C++ implementation following our strategy. Notice the helper functions valid and toLowerCase which encapsulate the logic for steps 1 and 2, making the main isPalindrome function much cleaner to read!

class Solution {
private:
    // Helper function to check if a character is alphanumeric
    bool valid(char ch) {
        if( (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9')) {
            return true; // It's a letter or a number
        }
        return false; // It's not alphanumeric
    }

    // Helper function to convert an uppercase character to lowercase
    // Assumes `ch` is already determined to be an alphanumeric character
    char toLowerCase(char ch) {
        if( (ch >='a' && ch <='z') || (ch >='0' && ch <='9') ) {
            return ch; // Already lowercase or a digit
        } else { // Must be an uppercase letter 'A'-'Z'
            // ASCII trick: 'a' - 'A' gives the difference,
            // adding this difference to an uppercase char converts it to lowercase.
            char temp = ch - 'A' + 'a'; 
            return temp;
        }
    }

public:
    bool isPalindrome(string s) {
        string temp = ""; // Our clean string container

        // Step 1: Filter alphanumeric characters
        for(int i = 0; i < s.length(); i++) {
            if(valid(s[i])) {
                temp.push_back(s[i]); // Add valid chars to our temp string
            }
        }

        // Step 2: Convert all characters in temp to lowercase
        for(int i = 0; i < temp.length(); i++) {
            temp[i] = toLowerCase(temp[i]);
        }

        // Step 3: Two-pointer palindrome check
        int s_idx = 0;                  // Pointer at the start
        int e_idx = temp.length() - 1;  // Pointer at the end

        while(s_idx <= e_idx) { // Loop until pointers meet or cross
            if(temp[s_idx] != temp[e_idx]) {
                return false; // Mismatch found, not a palindrome
            }
            s_idx++; // Move start pointer forward
            e_idx--; // Move end pointer backward
        }

        return true; // If we made it here, no mismatches were found!
    }
};

⏱️ Time & Space Complexity Analysis

Understanding how efficient your code is crucial in competitive programming!

Time Complexity: O(N)
- We iterate through the original string s once to filter characters (O(N)).
- We iterate through the temp string once to convert to lowercase (O(N) in the worst case, as temp can be as long as s).
- We iterate through the temp string again with two pointers to check for palindrome (O(N)).
- Since N is the length of the input string s, and all operations are linear, the total time complexity is O(N). Excellent!
Space Complexity: O(N)
- We create a new temp string to store the filtered and lowercased characters. In the worst case (e.g., s = "abcdefg"), temp will contain almost all characters from s.
- Therefore, the space complexity is O(N).

🌟 Key Takeaways

Problem Decomposition: Break down a complex problem into smaller, manageable steps (filtering, converting case, then checking).
Helper Functions: Use private helper functions (valid, toLowerCase) to keep your main logic clean and readable. This is a common practice for good code organization!
Two-Pointer Technique: An incredibly versatile algorithm for problems involving lists, arrays, or strings where you need to compare elements from opposite ends or find pairs.
String Pre-processing: Often, the first step in string problems is to clean or normalize the input according to the problem's rules.
Edge Cases: Always consider empty strings or strings with only one character. Our solution handles "" (empty string after cleaning) correctly by returning true.

This problem is a fantastic stepping stone for mastering string manipulation and fundamental algorithm techniques. Keep practicing, and you'll be crushing more complex problems in no time! Happy coding! 💻✨

Author Account: Vansh2710 | Published: 2026-03-30 00:03:37