[Java] Longest palindromic substring

Here's another string problem: given a string, find its longest palindromic substring.

The first character in the string, is always the center of a palindrome of length 1, therefore we can start investigating from the second position (if it exists).

For any string length > 1, our palindromic substring could be centered on any odd position (any character in the string) or even position (between any two characters in the string).

We can therefore for each position search in the string for the longest palindromic string centered there. We do this in O(N^2) time and constant space by looping over each character in the string and executing two separate loops expanding outwards from the current position.

When searching for odd length palindromes, we start with both indices for the inner loop on the current character, and for even length palindromes we set the start index on the character BEFORE us.

The inner loop breaks when the characters pointed at by the two indices are different, since we are NOT nesting these loops but execute them in a sequence their cost is O(N+N) which is O(N). The outer loop is O(N), therefore the total cost is O(N ^2)

You can check my implementation of longestPalindromicSubstring on my Gist along with some tests in LongestPalindromicSubstringJTests.