Longest Palindromic Substring

The problem, simply

You get a word. Find the longest piece of it, with no letters skipped, that reads the same from left to right and from right to left. Give back that piece.

A piece with no gaps is a substring, and a word that reads the same both ways is a palindrome. So this is the longest palindromic substring.

A story to remember it

Picture it

Examples

Way 1: the simple way

Check every piece.

1. For every start i and every end j >= i, take the piece s[i..j].
2. Check if it is a palindrome with two fingers walking inward.
3. Keep the longest one.

class Solution {
    public String longestPalindrome(String s) {
        int bestStart = 0, bestLen = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                int len = j - i + 1;
                if (len > bestLen && isPalindrome(s, i, j)) {
                    bestStart = i;
                    bestLen = len;
                }
            }
        }
        return s.substring(bestStart, bestStart + bestLen);
    }

    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;   // the two sides differ
            l++;
            r--;
        }
        return true;
    }
}

How long it takes: about n^2 / 2 pieces and up to n steps to check each, O(n^3). Extra room: a few counters, O(1) (no substrings are copied until the end).

Way 2: the clever way

Grow palindromes from their middle instead.

1. For every index i, try a one letter middle: L = R = i.
2. Also try a two letter middle: L = i, R = i + 1.
3. While L and R are inside the word and s[L] == s[R], move L left and R right.
4. When they stop, the palindrome is s[L + 1 .. R - 1], of length R - L - 1. Keep the longest.

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) return "";
        int bestStart = 0, bestLen = 0;
        for (int i = 0; i < s.length(); i++) {
            int odd = grow(s, i, i);          // middle is one letter
            int even = grow(s, i, i + 1);     // middle is a gap
            int len = Math.max(odd, even);
            if (len > bestLen) {
                bestLen = len;
                bestStart = i - (len - 1) / 2;   // works for both odd and even
            }
        }
        return s.substring(bestStart, bestStart + bestLen);
    }

    private int grow(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;                               // spread the wings
            r++;
        }
        return r - l - 1;                      // length of the palindrome found
    }
}

How long it takes: 2n - 1 middles, and each can grow up to n / 2 steps, O(n^2). On most real words the wings stop fast, so it runs much quicker than that. Extra room: a few counters, O(1).

Another way: the yes or no table

This is the dynamic programming view. Let P[i][j] be true if s[i..j] is a palindrome. A piece is a palindrome when its two end letters match and the piece inside is a palindrome (or has 0 or 1 letters). Fill the table from short pieces to long ones.

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n == 0) return "";
        boolean[][] P = new boolean[n][n];
        int bestStart = 0, bestLen = 1;
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                P[i][j] = s.charAt(i) == s.charAt(j) && (len <= 2 || P[i + 1][j - 1]);
                if (P[i][j] && len > bestLen) {
                    bestLen = len;
                    bestStart = i;
                }
            }
        }
        return s.substring(bestStart, bestStart + bestLen);
    }
}

It also takes O(n^2) time, but it needs O(n^2) room for the table. The table is worth knowing because the same P is reused in other problems, like palindrome partitioning and counting palindromic substrings.

Watch out for

• After the loop stops, L and R point one step past the palindrome. The length is R - L - 1, not R - L + 1.
• The start index is i - (len - 1) / 2. Check it on both an odd and an even example.
• Substring, not subsequence. For "agbcba" the answer here is "bcb", but the longest palindromic subsequence is "abcba".
• Empty input: return "" before the loop.

What interviewers ask next

• Can you do it in O(n)? Yes, with Manacher's algorithm. It reuses the mirror image of wings found earlier so each letter is grown past only once. Know that it exists and the idea; few interviews ask you to code it.
• Count all palindromic substrings: grow from every middle and add 1 for every successful step. Same O(n^2).
• Shortest palindrome by adding letters at the front: find the longest palindrome that starts at index 0, using KMP on s + '#' + reverse(s).
• Palindrome partitioning (fewest cuts): build the P table, then a 1D DP over cut positions.

Remember this

Grown-up words: the butterfly body is the center, spreading wings is expand around center, the piece is a palindromic substring, the yes or no table is the boolean DP table, and the O(n) trick is Manacher's algorithm.