Write a program to find the longest Palindrome in a string - Longest palindromic Substring

The problem, simply

A palindrome reads the same from left to right and from right to left, like racecar or abba. You get a string s. Find the longest piece of it, letters next to each other, that is a palindrome.

If two pieces tie for longest, give back the one that starts first. Every single letter is a palindrome, so for a non empty string the answer always has at least one letter.

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 with j >= i, test if s[i..j] is a palindrome by walking two fingers in from both ends.
2. Keep the longest one that passes.

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

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;   // ends differ
        }
        return true;
    }
}

How long it takes: about n^2 / 2 pieces, and each test can take n steps, so O(n^3). Extra room: a few numbers, O(1).

Way 2: the clever way

Every palindrome has a middle. Instead of testing pieces from the outside in, grow them from the inside out.

1. There are 2n - 1 places for the mirror: on each of the n letters (odd length) and in each of the n - 1 gaps (even length).
2. For each place, set left and right on the mirror and step outwards while both are inside the string and s[left] == s[right].
3. When they stop, the palindrome is everything strictly between them, of length right - left - 1.
4. Keep the longest.

Growing stops at the first mismatch, so we never waste time on pieces whose middle is already wrong.

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;
        int start = 0, maxLen = 1;
        for (int i = 0; i < n; i++) {
            int odd = grow(s, i, i);          // mirror on letter i
            int even = grow(s, i, i + 1);     // mirror in the gap after letter i
            int len = Math.max(odd, even);
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;    // works for both odd and even
            }
        }
        return s.substring(start, start + maxLen);
    }

    // step outwards while both hands see the same letter
    private int grow(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;              // letters strictly between the hands
    }
}

How long it takes: 2n - 1 mirrors, and each can grow up to n / 2 steps, so O(n^2). The worst case is a string like aaaa...a. Extra room: a few numbers, O(1).

Another way: Manacher's algorithm

Manacher's algorithm finds the answer in O(n). Two tricks:

• Put a # between all letters, so abba becomes #a#b#b#a#. Now every palindrome is odd, and you only need mirrors on letters.
• A palindrome is a mirror. If you are inside a big palindrome that you already know, the letter at your mirror image on the left side already tells you how far you can grow, at least up to the big palindrome's edge. You start growing from there, not from zero.

class Solution {
    public String longestPalindrome(String s) {
        StringBuilder t = new StringBuilder("^");     // ^ and $ are walls that never match
        for (char c : s.toCharArray()) t.append('#').append(c);
        t.append("#$");
        int[] p = new int[t.length()];                // p[i]: how far the palindrome at i reaches
        int center = 0, right = 0;                    // the palindrome reaching furthest right
        for (int i = 1; i < t.length() - 1; i++) {
            if (i < right) p[i] = Math.min(right - i, p[2 * center - i]);  // copy the mirror image
            while (t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) p[i]++;
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }
        int bestLen = 0, bestCenter = 0;
        for (int i = 1; i < t.length() - 1; i++) {
            if (p[i] > bestLen) {
                bestLen = p[i];
                bestCenter = i;
            }
        }
        int start = (bestCenter - bestLen) / 2;       // back to positions in s
        return s.substring(start, start + bestLen);
    }
}

The right edge only moves forward, and every step of growing pushes it, so the total work is O(n). Extra room: the new string and p, O(n). This code assumes ^, # and $ do not appear in s.

Watch out for

• The start index. For a palindrome of length len around i, the start is i - (len - 1) / 2. Check it on one odd and one even case.
• Confusing substring with subsequence. Here the letters must be next to each other. The longest palindromic subsequence is a different problem that needs a 2D table.
• Off by one in grow. When the loop stops, left and right are one step past the palindrome, so the length is right - left - 1.
• The empty string and a single letter. Return s itself.

What interviewers ask next

• Can you use a table instead? Yes: dp[i][j] is true if s[i] == s[j] and dp[i + 1][j - 1] is true. It is O(n^2) time and O(n^2) room, so expanding is better.
• Count all palindromic pieces (LeetCode 647). Same mirrors, but add one for every successful step instead of keeping the max.
• Can you do better than O(n^2)? Yes, Manacher's algorithm above runs in O(n). Hashing with binary search on the length gives O(n log n).
• Longest palindromic subsequence. It is the longest common subsequence of s and its reverse, O(n^2).
• Shortest palindrome by adding letters in front. Find the longest palindrome that starts at index 0, often with KMP on s + '#' + reverse(s).

Remember this

Grown-up words: the mirror is the center of the palindrome, the two hands are two pointers expanding outwards, odd and even cases are letter centers and gap centers, and the fast version is Manacher's algorithm.