Repeat Code with Leetcode — Palindromic Substrings

At the risk of butchering a famous literature and movie quote, the rabbit hole goes deep when it comes to this problem. Your task is to find the number of palindromic substrings inside of an input string, and just to give you a preview of how much thought people have put into this question, here is a ScienceDirect paper that appeared in “Journal of Discrete Algorithms” titled “A subquadratic algorithm for minimum palindromic factorization.” From the paper’s introduction:

For example, Manacher [13] gave a linear-time algorithm for listing all the palindromic prefixes of a string. Apostolico, Breslauer and Galil [3] observed that Manacher’s algorithm can be used to list in linear time all maximal palindromic substrings, which are those that cannot be extended without changing the position of the center. Other linear-time algorithms for this problem were given by Jeuring [10] and Gusfield.

The only reason I included the quote above is because it names off people who have researched the topic. This post is going to be on a variation of the Manacher Algorithm, and it is kind of cool to me that it has a name.

The Problem

Name: Palindromic Substrings, or Leetcode 647

Difficulty: Medium

Topics covered: String manipulation

Topics NOT covered if you solve it this way: Recursion, Dynamic Programming

Problem Description: Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

The solution I will present is simply my C++ equivalent of this excellent Java solution on Leetcode. The Neetcode video above is great, and the Leetcode discussion answer is great, and this OpenGenus IQ article is great…and it just so happens that they are all using essentially the same method but in different programming languages (Python, Java, and C++ respectively). I do not want this to just be a reference aggregate, which would be hard to read, so let me do my best to summarize the method that all three of them use.

First of all, the brute-force solution may come to mind. This is how Shreya Shah in OpenGenus initially solves it, and at the risk of immediately being disqualified from all future interviews at all companies…I like this solution a lot and think that it is really clear, from how she coded it. Basically, you write a helper function to determine if a string is a palindrome. You then use a double-for loop to check every possible substring. For the input string racecar, you would check the letter ‘r’ (single-letter words are palindromes), then ‘ra’, then ‘rac’ until the end of the word…then you would iterate to ‘a’ and try ‘ac’, ‘ace’…

This solution works, and I really like it, but apparently no major tech company would. The running-time complexity is O(n³). Determining if a string is a palindrome is O(n). There are O(n²) possible substrings, so by her own description and explanation, Shah’s first solution would be O(n³).

First Digression: Asymptotic Time Complexity

If you are new to this blog and are also relatively new to coding interviews, you will notice that I suddenly started including asymptotic time complexity like it was some universally accepted part of human conversation. It is not. It can get fairly complex, and if you do not know what it is then you should probably read up on it (Cracking the Coding Interview has the best explanation, in my opinion), but I do think people have a tendency to make it sound way more confusing than it actually is. Even the term is kind of off-putting. Asymptotic time complexity. “Algorithm” used to be a word that only programmers and scientists seemed to use, until every YouTube star and their 1000th subscriber started to talk about it.

I once explained binary search to my dad. I said that I have 100 items, and that they are not in order; I asked him how many items you would have to check, in the worst-case scenario, to find one that I was looking for. His answer was that you would need to check 100 items.

And that is correct. The asymptotic time complexity of linear search is O(n).

But the asymptotic time complexity of binary search, which you can apply to a sorted list, is O(lg n). In the worst possible case, you would need to perform lg n operations to find the item. That is a huge improvement.

Was that also confusing? You can read about it in more detail on Khan Academy. Cracking the Coding Interview, though, goes into many more cases…including some traps you may fall into when attempting to determine asymptotic time complexity.

The Manacher Algorithm variation can achieve a running-time complexity of O(n²). You are welcome to give this a try, but here is how it works:

  • Consider the work that was performed in the brute-force solution. This was a lot of repeated work
  • Consider a palindrome like the word racecar. You can think of a palindrome as a center, and then expand from the center. ‘e’ is a palindrome. So is ‘cec’, and so is ‘aceca’
  • Instead of writing a helper function that determines if an input string is a palindrome, write a helper function that counts palindromes by expanding from the center. It takes a center index as its input. It keeps expanding as long as the first and last letter match, and as long as it does not go out of bounds
  • Consider that you need to account for both strings of even length and odd length. You can do so by treating two letters as the center

That is pretty much it…we can cover the dynamic programming solution another time. But first, here is one more digression:

Second Digression: Global Variables

The Java solution has a global variable and my code does not. Does it matter? I would argue that for a problem like this it does not, a little bit like how using namespace std; is generally bad practice in C++ but is also auto-included in some coding interviews. Global variables can make code less readable and can lead to other problems as well. Here we may as well not use it, but I do think it opens some interesting debates.

When we got out of college, they hammered us with rules like never, ever use global variables. For the most part this is good advice, but it is important to know why.

I find the whole topic of interview criteria pretty interesting because companies can hypothetically do anything they want…within reason. Maybe only attempting to code the brute-force solution is an automatic rejection. Maybe your ability to code on the spot is less important than your ability to explain design patterns. At CORGICorporation, all we do is show you clips of Maxine the Corgi and then count the number of times you say “awwh.”

Closing Thoughts

I find purely technical articles kind of boring, even though this is what most people I know in the field would prefer. Where is the motivation? How do I recharge my batteries? Coding interviews can be quite stressful, and the worst obstacle in the process is that voice in our heads telling us that if we blow this, everything we want is going to vanish. The typical 45 minutes should be enough time for these challenges, but it will pass in an instant if you are unable to silence the doubtful voice in your head instead of training it to feed you relevant algorithms and useful data structures.

I thought I would close every article in this series, then, with a little bit of fluff (or a lot, depending on my mood).

Manacher published his algorithm in the year 1975. More academics followed and made their own contributions, including the solutions to this problem. So this is actually a subject of conversation for some of the greatest minds in the field, not just some arbitrary brain teaser invented by Google to filter out candidates in the year 2021 before Reddit users have a chance to condescend to people who cannot solve it. The related question also has some real-world applications…I guess…

For the time being, I suppose the most relevant real-world application is if you see a similar problem on an interview.

--

--

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