Problem 🤔

Palindrome Definition a word, phrase, or sequence that reads the same backward as forward, e.g., madam or nurses run.

Given a string, write a function to check if the string is a palindrome, or if the letters can be rearranged to form a palindrome.

Note When checking for a palindrome you can ignore empty spaces.

Real World Applications 🌎

Another way of looking at this is understanding if a string is symmetric when examining from start to end. I haven’t found many real world applications for this! However, it is a common interview question and concept worth internalizing.

The Finer Details 🔎

Let’s have a better understanding of which types of strings can be a palindrome!

bob is a palindrome, because it reads the same back to front. In this string, every letter appears an even amount of times, except for the middle letter which appears an odd amount of times.

Same goes for race car! (Remember, we’re ignoring empty spaces when searching for palindromes).

goog is a palindrome, because it reads the same back to front. In this string, every letter appears an even amount of times.

Can you think of valid palindromes which fall into different categories? Actually, these are the only two cases in which a valid palindrome will fall into! You can try to work through more palindromes and see that all of them fall into these categories.

A great way to do this is keep track of how many times we see each letter! When we’re doing iterating over the string we can confirm whether or not the given input falls into our valid palindrome categories.

Solution 💡 - Optimal

Complexity Analysis 🧮

Time complexity

O(n)

Loop over input once

Space complexity

O(n)

Seen data set to count occurrences.

Takeaways 🎉🥳

The challenging part of this question is formulating the categoreis that represent a palindrome. Don’t rush to start coding! Take time to understand the traits of a palindrome and the rest is easy!

Resources 📚 💻

Leetcode Cracking the Coding Interview (CTCI) 1.4