1. Longest Palindromic Substring

My friend is solving some LeetCode problems now, and I couldn't help but join him.

I know, I know... LeetCode is dead, all this is trash, and we shouldn't solve it. But for now the standards of interviews in Big Tech are settled, and you can, at least, laugh at us, who spend tons of time performing cargo cult rituals.

First of all, it's like a 20-minute problem. In these 20 minutes you have to:

— 0 min
✒️ read the problem statement
✒️ come up with a few test cases - it helps both to understand the problem better and to have test cases for the later testing session
✒️ figure out a working solution for the problem
✒️ explain your approach to the interviewer, give them T=O(...), M=O(...) estimations
✒️ get approval from the interviewer to go on with this solution

  • 5 min
    ✒️ implement your approach
    ✒️ test your implementation on your test cases
    ✒️ fix it, if necessary
    ✒️ check that your T=O(...), M=O(...) are true

  • 18 min
    ✒️ discuss pros and cons

  • 20 min

I'm not a quick thinker, and in order to be able to take part in this competition, I thought a lot and came up with some tricks which I want to share. First of all, how to read the statement and how to approach a solution.

"the longest palindromic substring" - if you, like me, start to think "I read really beautiful algorithms which solve it in linear time, what was that book..." - poof, you have already lost this game. Nice thought. But you have to mention it really quickly and move on. What is the real complexity you want to aim at? Check s.length <= 1000 and think about the naive approach. All substrings - n squared, palindrome check - n => n cubed. Rough estimation for time - 10 secs in Python - doesn't look good.

Here you have to recall at least a glimpse of that wonderful algorithm you read about. There was something... about... middle points of palindromes! Let's check. n middle points, linear check => n squared. 0.01s for n = 1000. Sounds promising.

In the program I want to share a trick: decomposition. Of course, you can try to write a program in one long sheet of text. But if you split it into logical parts, it's better for you. Python gives you a great opportunity - iterators. In the function you can generate candidates and then select the best using just the max function.

In order to use just max, we are to be careful about an empty sequence. It is not a case here, because n >= 1. If an empty sequence is possible, default = ... in the max function is your friend.

For odd-length palindromes, candidate generation is quite boring. We start with the trivial one-letter palindrome and extend it, if it is possible. No problem.

Even-length palindromes have a real chance to be absent at all. One more trick - make a step back and set up variables in the previous position before they form a valid even palindrome. Then we can check whether the variables are still in this weird initial position. If they are, we don't have a candidate.

So, here we are. A few tricks, and the problem is solved.