Problem 5 - Longest Palindrome Substring (Medium)
Code for this problem can be found at https://github.com/scprogramming/LeetcodeExplained/tree/master/Problem%20Five%20-%20Longest%20Palindrome%20Substring%20(Medium)
Problem: Given a string s, find the longest palindrome that is a substring of s.
Your first approach to this problem might be to decide to generate all the substrings of s, determine which ones are palindromes, and of those, pick the longest substring. This idea does work; however, it is not the best solution that can be done for this problem.
Consider an example input string, "badad". We can see that this has two longest substrings, "bab" and "aba". We will assume for this problem that we just want any single palindrome that is of the maximum length, so either solution is valid.
If we want to try to locate the longest palindrome, one solution we could use is to start at the middle and expand outwards. If we did this, we would see the following strings:
We would fail at badad, and return ada as the maximum palindrome substring. This strategy appears to work for this case, but let's do a little more analysis to verify it works in general. To understand why this idea works, consider how palindromes exactly work. Since palindromes are mirrored around a center, working from the center guarantees that we will capture all possible palindromes, and stop only when no more palindromes can exist.
This means that rather than generating every substring, we only pick midpoints in the string, and expand until palindromes aren't found. This saves us a few operations and allows us to compute the solution faster. If we can start at a midpoint that gives us even length substrings, and one that gives us odd length substrings, we can find the largest odd and even length palindromes. This in turn will give us the largest palindrome in general, since the combination of those two sets will give us all palindromes. This approach takes the brute force method, and basically adds a stopping condition as soon as we fail to make a palindrome. Let's see how this is coded.
I will start with the first loop of generating palindromes in the program.
We start by setting a low point as the start of the array, and a high point directly in front of it. We then iterate while we still have a palindrome, decrementing the low end and incrementing the high end. While this is happening, we are checking if the current palindrome is longer than the last max one we found, and if so, we track the location of it. We do something similar with our second loop, except we start at one before and one after the current location of i.
Once this is completed, we will have checked every possible palindrome, giving us the longest palindrome substring of the provided string.
Now that we have a working solution, let's discuss the time complexity of it. Since we iterate the whole string, and then iterate it again within that loop, we do a total of n2 iterations in the worst case. Therefore, our algorithm is O(n2). The typical techniques to generate all substrings and verify palindromes is O(n3), so this is faster by a factor of n.