Longest Palindrome In String Solution
Table of Contents
Approach 2: Expand From Middle
Solution
Approach 1: Brute Force
The trivial solution would be to generate every possible substring and for each substring pass it into an isPalindrome function which will check if the substring is a palindrome. While this is happening you would use one additional variable to keep track of the longest palindrome you have seen so far.
The time complexity of this function would be O(n3) where n is the length of the string. This is because the first nested for loop in the function longestPalindrome would cost O(n2) to run and the additional call to the isPalindrome function would be O(n).
The space complexity of this would be O(1) because we don’t use any additional space that is dependent on the size of the string.
This solution is a good start to the problem and can cover all the test cases but in an interview this solution wouldn’t be accepted.
Approach 2: Expand From Middle
We can build on top of the brute force solution to come up with something better. We notice that a palindrome has a middle point that is mirrored on the left and right side. Therefore, we can find a palindrome from taking any point in the string, s, and expanding from the center to find the longest palindrome.
There are a total of 2n - 1 centers because a palindrome can be of odd length where the center is a letter or a palindrome can be of even length where the center is in between two letters.
The resulting time complexity would be O(n2) with O(1) space complexity.
The code looks like this:
Approach 3: Other Solutions
There is a dynamic programming solution that has a time complexity of O(n2) with O(n2) space complexity but we won’t cover this because the solution above is better and will be accepted in an interview scenario.
The most optimal solution for this problem is called Manacher’s Algorithm that has O(n) time complexity. This solution is non-trivial and won’t be expected in an interview scenario, but if you’re curious you can check it out here.