Longest Palindromic Substring LeetCode Be Crazy
Strive not to be a success, but rather to be of value. — Albert Einstein
Let me start off by saying Holy Shit. This one is now very well understood. Rule number one to “Cracking the code”… Start off with a naive approach. I spent a meaningful amount of my life trying to make this code O(nlogn) vs the very (simple?) O(n²) solution; I will be going over both in the lines below.
So, Longest Palindromic Substring, Leet Code problem number 5. You are given a string between 0–1999 characters and are asked to look through it and return the longest “Palindromic” substring.
For our brute force solution, basically we are going to look for each and every possible string combination, check if it is a palindrome, if it is a palindrome we will check to see if it is longer than any previous palindrome substrings; AND, if it is, were gonna set it to our longest substring variable/ binding.
So, take a second and think about what elements, variables, function… this algorithm will need.
We will need to check all possible inner string combinations, so that means we will need two pointers, one to represent a start point and another the end;
We will need to move these pointers some how, maybe a few loops;
We will need to create a function to check if the string is the same forward as it is backwards.
And, we will need to compare our current valid palindrome to a “longest string” binding.
— Here we are taking in a string. — Setting a longest string variable — running through two for loops — checking to see if our current string is a palindrome — and setting longest to current if the current length is greater than the longest.
— We also have a palindrome check function that is taking in a string and if it is a palindrome it is returning true, if not false.
This is a, very-very, inefficient method of solving this problem. It works, but we are running through no only nested for-loops, but we are also using a function that will use a looping mechanism. (I was not super excited coming up with this..)
The “Better” solution if pretty similar in as we are looping and using a function to check if we are dealing with a palindrome, but this solution has a slightly different approach.
But first, i’m going to post the code i wrote that passed a majority of leetCodes tests; Take a second to look at it and understand what is going on; I will probably go back and refactor to make it work fully at a later time.
Let me just tell you, i was pumped up being able to implement recursion and understanding how exactly my code was operating on a slightly deeper level; I knew the issue i was dealing with; I could not wrap my head around how to implement it without completely rewriting my code.(just got really excited thinking I could just call slider a second time with the “even” markers set; but it was no good.
So without further ado, The Smart Way.
So same thing, we are taking in a string. but instead of holding the actual string, we are just going to keep track of our indexes; so we have current=[0,1];
Now lets jump down into our “getLongestPalindrome” function, this function will be taking in our string, and a left/right index; we make sure our left index is greater than zero, and our right index isn’t greater than our string length. Then, we do a second check to see if our strings value at “leftIndex” is equal to the string value of our “rightIndex” if no we break, if so, we increase our left and right index value…. Finally, we return an array holding our left and right index. remember, we created/instantiated our current index on the first line of our function.
Now, look back up at the code. We have two variables, one “odd” and the other “even”… odd is taking the index and passing the left value and right value relative to the current “i/index” value into our getLongestPalindrome function, while even is taking the index minus 1 and the index; each function will return the appropriate indexes. and we will use those to create a “longest” array; after we will subtract our longest indexes and current indexes, setting our current to which ever value is greater after subtracting.(take a second to digest all of that. i would recommend going back up and checking out the code, or go into your code editor and manually type everything out).
Finally, once we exit our for loop, we will return a string sliced at the appropriate indexes using [0,1]=current;
I hope you enjoyed this article, and I hope it gave some clarity to the longest palindromic substring. If you made it this far, add me on linkedIn at http://www.linkedin.com/in/adanieljohnson. i run a daily algorithms group, and you are more than welcome to come and learn, or teach. Lets Go!
