Longest Palindromic Substring

NeetCode: Longest Palindromic Substring · LeetCode: 5. Longest Palindromic Substring · Difficulty: Medium

Given a string s, return its longest palindromic substring. If several have the same length, any of them is accepted; the programs below return the leftmost.

Example

Text

Input:  s = "babad"    Output: "bab"   ("aba" is also valid)
Input:  s = "cbbd"     Output: "bb"

Brute force: check every substring

Try every pair (i, j), test whether the substring from i to j (exclusive) reads the same both ways, and remember the longest. There are O(n^2) substrings and each check costs O(n).

Java

class Solution {
    private boolean isPalindrome(String s, int i, int j) { // s[i..j), j exclusive
        int l = i;
        int r = j - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }

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

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.longestPalindrome("babad"));
        System.out.println(solution.longestPalindrome("cbbd"));
        System.out.println(solution.longestPalindrome("a"));
        System.out.println("[" + solution.longestPalindrome("") + "]");
    }
}

Output

bab
bb
a
[]

Time: O(n^3). Space: O(1) besides the returned substring. charAt reads a 16-bit char, so the check is exact for the letters and digits the problem allows.

Optimal: expand around each center

Every palindrome is symmetric around a center: a single character (odd length) or the gap between two characters (even length). There are 2n - 1 centers. From each one, grow outward with the indices l and r while the two ends match and stop at the first mismatch. Because the inside of a palindrome is also a palindrome, nothing is re-checked. A 2-D DP table gives the same O(n^2) time but needs O(n^2) space. expand returns the length of the palindrome it found, and the start index follows from the center: i - (len - 1) / 2.

Java

class Solution {
    // Returns the length of the widest palindrome centered between l and r.
    private int expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }

    public String longestPalindrome(String s) {
        int bestStart = 0;
        int bestLen = 0;
        for (int i = 0; i < s.length(); i++) {
            int odd = expand(s, i, i);
            if (odd > bestLen) {
                bestLen = odd;
                bestStart = i - (odd - 1) / 2;
            }
            int even = expand(s, i, i + 1);
            if (even > bestLen) {
                bestLen = even;
                bestStart = i - (even - 1) / 2;
            }
        }
        return s.substring(bestStart, bestStart + bestLen);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.longestPalindrome("babad"));
        System.out.println(solution.longestPalindrome("cbbd"));
        System.out.println(solution.longestPalindrome("a"));
        System.out.println("[" + solution.longestPalindrome("") + "]");
    }
}

Output

bab
bb
a
[]

Time: O(n^2) (2n - 1 centers, each expands at most n / 2 steps). Space: O(1) besides the returned substring. Manacher's algorithm runs in O(n).