The Blind 75 Leetcode Series: Valid Palindrome

Today, we are working on 125. Valid Palindrome

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.

We have a string, and we want to check if reading it from the front and reading it from the back produce the same result. One of the example actually showed it already, but we want to double check if we care about special characters and spaces, so things to ask about could be

  1. Do we care about special characters?
  2. Do uppercase and lowercase count as the same word?
  3. Spaces? What about spaces?

If the interviewer tells us that we only care about alphanumerical and it’s not case sensitive, then we can start.

Since we only care about alphanumerical, the intuition would be going through the string once and only take the alphanumerical.

Once we filter out the unwanted characters, we can simply check if the string read from front and read from back are the same. A simple s == s[::-1] will do the trick.

So, putting everything together, we have

def isPalindrome(s):
s_alnum = []
for letter in s:
if letter.isalnum():
s_alnum.append(letter.lower())
return s_alnum == s_alnum[::-1]

Now, this thing on the big-O perspective is optimal. Our time complexity is linear to the length of the string, so O(N), but we can see that we went through the string twice and we even created a new variable to store the alphanumerical.

def isPalindrome(s):
s_alnum = []
for letter in s: # O(N)
if letter.isalnum():
s_alnum.append(letter.lower())
return s_alnum == s_alnum[::-1] # O(N)

The extra variable, following our tradition, is not that big of a deal to worry about since memory is cheaper these days, but is it possible to go through the string just once and still do what we do?

We want to compare two characters, so it makes sense that we have 2 pointers. We start emerging these two pointers each time we find a matching pair or we find non-alphanumerical. Once the left pointer hits the right pointer, we stop. Also, every time we find a non-matching pair, we also stop and return False right away. There’s no need to continue once a non-matching pair shows up.

So, putting everything together we have

def isPalindrome(s):
i, j = 0, len(s) - 1
while i < j:
while not s[i].isalnum() and i < j: # it's possible i gets bigger than j, so this i < j has to be made
i += 1
while not s[j].isalnum() and i < j:
j -= 1
if s[i].lower() != s[j].lower():
return False
# move both pointers when we find a matching pair
i += 1
j -= 1
return True

What do we have now for time complexity?

It’s actually still O(N) for big-O, but now we only go through the string once. No extra linear space (but constant space for storing the 2 pointers), no extra loop, nothing.

def isPalindrome(s):
i, j = 0, len(s) - 1
while i < j: # O(N)
while not s[i].isalnum() and i < j: # this while loop never resets i and j, so still within the outer while loop
i += 1
while not s[j].isalnum() and i < j:
j -= 1
if s[i].lower() != s[j].lower():
return False
i += 1
j -= 1
return True

This is an entry level problem in my opinion, like a fizzbuzz.It’s very straightforward and nothing tricky about it. Your bruteforce approach can be improved upon inspection, meaning you don’t need a complete overhaul of your solution to find the optimal solution. If the interviewee uses the first approach, I consider it passed. Second approach is a plus for showing you’re picky about your solution. You want to optimize the efficiency to max. This is a good problem of “Can you code?” and you’ll most likely see it in the first round interview (phone screen). Some startups who can’t be too picky about the candidates might use this as well.

There you have it! Another problem down.

Buy my a coffee: https://www.buymeacoffee.com/jonathanckz

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jonathan Chao

Jonathan Chao

I am a software developer who has been in this industry for close to a decade. I share my experience to people who are or want to get into the industry