Tutorials on Advanced Math and Computer Science Concepts

# 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:

d