5. Longest Palindromic Substring

/**

 * 5. Longest Palindromic Substring

 * Given a string s, return the longest palindromic substring in s.

 * Example 1:

 * Input: s = “babad”

 * Output: “bab”

 * Note: “aba” is also a valid answer.

 * Example 2:

 * Input: s = “cbbd”

 * Output: “bb”

 */

See solution on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/LongestPalindromeSubstring.java

Palindrome based problems are frequently asked. This problem is asking for the longest possible palindrome in a string.

The first piece of puzzle is recognizing that palindromes can occur as either odd or even number of characters. For example ‘bab’ is a palindrome and so is ‘baab’.

The algorithm is based on:

1. Iterate the string left to right.
2. At each index check whether an odd or even length of palindrome exists.
3. Pick the larger of the even or odd length palindrome
4. Check its length against the previous max length calculated.
5. If its length is greater than the previous largest length, mark this palindrome as the longest palindrome.

One trick to the problem is calculating the start index of the palindrome based on current index and length. The length of palindrome needs to be split in half since palindrome is symmetric around center and that value subtracted from current index. However, you need to subtract one from the length before diving it by 2. This equation can be visualized by drawing out the string and indexes on white board.  

-i,e start index = “start = i – (maxLen – 1) / 2”.

Here is the code:

public static String longestPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return "";
    }
    int start = 0;
    int end = 0;
    for (int i = 0; i < s.length(); i++) {
        int sizeOdd = centerPalindrome(s, i, i);
        int sizeEven = centerPalindrome(s, i, i + 1);
        int maxLen = Math.max(sizeEven, sizeOdd);
        if (maxLen > end - start) {
            start = i - (maxLen - 1) / 2;
            end = start + maxLen;
        }
    }
    return s.substring(start, end);
}

static int centerPalindrome(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}