Hello and welcome back brave human being.

Before we delve into the problem, I want to thank you for returning every day and working on your LeetCode skills.

The current status of the tech industry has shown us that there is no longer a concept of job security.

However, true job security lies in skill security; the ability to secure another job.

Working on your LeetCode skills is what is going to give you the ability to switch jobs in Tech or get another job after getting laid off.

Let’s get back into it.

Day 6: 125. Valid Palindrome

Determine if a given string is a palindrome. A palindrome is a sentence that reads the same forward and backward.

There are many ways to solve this but we are only thinking about a two-pointer solution. A two-pointer solution does not need an extra data structure and it iterates through the string only once, making it an optimized solution.

Whether we advance our Left and Right pointers depends on whether they are alphanumerical or not.

If they are, are they equal?

If they are not equal, we immediately know it is not a palindrome. Otherwise, we advance our pointers.

Here is an example…

Final Solution

Day 6: 125. Valid Palindrome

        
            #include <iostream>
            #include <cctype>
            #include <string>

            class Solution {
            public:
                bool isPalindrome(string s) {
                    int L=0;
                    int R=s.length()-1;
                    while(L<=R){
                        if(!isalpha(s[L])&&!isdigit(s[L])){
                            L++; // we skip L
                        }
                        else if(!isalpha(s[R])&&!isdigit(s[R])){
                            R--; // we skip R
                        }
                        else if (tolower(s[R])==tolower(s[L])){
                            L++;
                            R--;
                        }
                        else{
                            return false; // It is not a palindrome
                        }
                    }
                   return true; // It is a palindrome!
                }
            };
        
    

Let’s pause to go over the time complexity of this simple get genius solution…

Our Left pointer will iterate through the first half of the string and our Right pointer will iterate through the last half of the string, only iterating once.

This solution will result in an O(N) Time Complexity with no extra memory needed.

RED FLAGS IN YOUR INTERVIEW SEARCH!