Longest palindromic substring

Lesson · 10 min read · Dynamic programming · Longest palindromic substring

The longest contiguous palindrome. A boolean table over intervals, or the simpler O(1)-space expansion around every centre.

A feasibility table

Now the palindrome must be contiguous. Let pal(i, j) be true if s[i..j] is a palindrome. It is when the ends match and the inside is a palindrome:

Recurrence

pal(i, j)

s[i] = s[j] and (j − i < 2 or pal(i + 1, j − 1)).

answer

the longest interval with pal(i, j) true.

The operators here are and along a choice and no choice at all: this is a feasibility table rather than an optimisation, filled by increasing length like every interval DP.

pal(i, j) for babad, by length. T = true, F = false.

Step 1 / 16

Base cases filled first.
Step 2 / 16

[0, 0] "b": a palindrome.
Step 3 / 16

[1, 1] "a": a palindrome.
Step 4 / 16

[2, 2] "b": a palindrome.
Step 5 / 16

[3, 3] "a": a palindrome.
Step 6 / 16

[4, 4] "d": a palindrome.
Step 7 / 16

[0, 1] "ba": not a palindrome.
Step 8 / 16

[1, 2] "ab": not a palindrome.
Step 9 / 16

[2, 3] "ba": not a palindrome.
Step 10 / 16

[3, 4] "ad": not a palindrome.
Step 11 / 16

[0, 2] "bab": a palindrome.
Step 12 / 16

[1, 3] "aba": a palindrome.
Step 13 / 16

[2, 4] "bad": not a palindrome.
Step 14 / 16

[0, 3] "baba": not a palindrome.
Step 15 / 16

[1, 4] "abad": not a palindrome.
Step 16 / 16

[0, 4] "babad": not a palindrome. The longest true interval is [0, 2], "bab" ([1, 3], "aba", is as long; the first is reported).

Expanding around centres

Every palindrome has a centre: a character (odd length) or a gap between two characters (even length). There are 2n − 1 centres. Expanding outwards from each while the ends match finds the longest palindrome around it, using the same fact as the table (matching ends around a palindrome) without storing the table.

def longest_palindrome(s):
    best = (0, 0)                              # [start, end) of the best so far
    for centre in range(2 * len(s) - 1):
        lo, hi = centre // 2, (centre + 1) // 2
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo, hi = lo - 1, hi + 1
        if hi - lo - 1 > best[1] - best[0]:
            best = (lo + 1, hi)
    return s[best[0]:best[1]]

std::string longest_palindrome(const std::string& s) {
    int n = s.size(), best_lo = 0, best_hi = 0;          // [start, end) of the best so far
    for (int centre = 0; centre < 2 * n - 1; ++centre) {
        int lo = centre / 2, hi = (centre + 1) / 2;
        while (lo >= 0 && hi < n && s[lo] == s[hi]) { --lo; ++hi; }
        if (hi - lo - 1 > best_hi - best_lo) { best_lo = lo + 1; best_hi = hi; }
    }
    return s.substr(best_lo, best_hi - best_lo);
}

static String longestPalindrome(String s) {
    int n = s.length(), bestLo = 0, bestHi = 0;          // [start, end) of the best so far
    for (int centre = 0; centre < 2 * n - 1; centre++) {
        int lo = centre / 2, hi = (centre + 1) / 2;
        while (lo >= 0 && hi < n && s.charAt(lo) == s.charAt(hi)) { lo--; hi++; }
        if (hi - lo - 1 > bestHi - bestLo) { bestLo = lo + 1; bestHi = hi; }
    }
    return s.substring(bestLo, bestHi);
}

function longestPalindrome(s) {
    let bestLo = 0, bestHi = 0;                          // [start, end) of the best so far
    for (let centre = 0; centre < 2 * s.length - 1; centre++) {
        let lo = Math.floor(centre / 2), hi = Math.floor((centre + 1) / 2);
        while (lo >= 0 && hi < s.length && s[lo] === s[hi]) { lo--; hi++; }
        if (hi - lo - 1 > bestHi - bestLo) { bestLo = lo + 1; bestHi = hi; }
    }
    return s.slice(bestLo, bestHi);
}

fn longest_palindrome(s: &str) -> &str {
    let b = s.as_bytes();
    let n = b.len() as i64;
    let (mut best_lo, mut best_hi) = (0usize, 0usize);   // [start, end) of the best so far
    for centre in 0..(2 * n - 1).max(0) {
        let (mut lo, mut hi) = (centre / 2, (centre + 1) / 2);
        while lo >= 0 && hi < n && b[lo as usize] == b[hi as usize] { lo -= 1; hi += 1; }
        if (hi - lo - 1) as usize > best_hi - best_lo { best_lo = (lo + 1) as usize; best_hi = hi as usize; }
    }
    &s[best_lo..best_hi]
}

longestPalindrome :: String -> String
longestPalindrome s = take (hi - lo) (drop lo s)
  where
    n = length s
    a = listArray (0, n - 1) s
    -- expand from each of the 2n - 1 centres, keeping the widest [start, end)
    expand l h
      | l >= 0 && h < n && a ! l == a ! h = expand (l - 1) (h + 1)
      | otherwise = (l + 1, h)
    (lo, hi) = foldl wider (0, 0) [ expand (div c 2) (div (c + 1) 2) | c <- [0 .. 2 * n - 2] ]
    wider (bl, bh) (l, h) = if h - l > bh - bl then (l, h) else (bl, bh)

Implementation

The problem in this module, solved by expansion in six languages:

def longest_palindrome(s):
    best_lo, best_hi = 0, 1                   # best palindrome is s[best_lo:best_hi]
    for centre in range(2 * len(s) - 1):      # characters and the gaps between them
        lo, hi = centre // 2, (centre + 1) // 2
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        if hi - lo - 1 > best_hi - best_lo:   # strictly longer keeps the earliest
            best_lo, best_hi = lo + 1, hi
    return s[best_lo:best_hi]

#include <string>

std::string solve(std::string s) {
    int bestLo = 0, bestHi = 1, n = s.size();
    for (int centre = 0; centre < 2 * n - 1; ++centre) {
        int lo = centre / 2, hi = (centre + 1) / 2;
        while (lo >= 0 && hi < n && s[lo] == s[hi]) { --lo; ++hi; }
        if (hi - lo - 1 > bestHi - bestLo) { bestLo = lo + 1; bestHi = hi; }   // strictly longer
    }
    return s.substr(bestLo, bestHi - bestLo);
}

class Solution {
    public String longestPalindrome(String s) {
        int bestLo = 0, bestHi = 1, n = s.length();
        for (int centre = 0; centre < 2 * n - 1; centre++) {
            int lo = centre / 2, hi = (centre + 1) / 2;
            while (lo >= 0 && hi < n && s.charAt(lo) == s.charAt(hi)) { lo--; hi++; }
            if (hi - lo - 1 > bestHi - bestLo) { bestLo = lo + 1; bestHi = hi; }   // strictly longer
        }
        return s.substring(bestLo, bestHi);
    }
}

function longestPalindrome(s) {
  let bestLo = 0, bestHi = 1;
  for (let centre = 0; centre < 2 * s.length - 1; centre++) {
    let lo = centre >> 1, hi = (centre + 1) >> 1;
    while (lo >= 0 && hi < s.length && s[lo] === s[hi]) { lo--; hi++; }
    if (hi - lo - 1 > bestHi - bestLo) { bestLo = lo + 1; bestHi = hi; }   // strictly longer
  }
  return s.slice(bestLo, bestHi);
}

fn solve(s: &str) -> String {
    let c: Vec<u8> = s.bytes().collect();
    let n = c.len() as i64;
    let (mut best_lo, mut best_hi) = (0i64, 1i64);
    for centre in 0..2 * n - 1 {
        let (mut lo, mut hi) = (centre / 2, (centre + 1) / 2);
        while lo >= 0 && hi < n && c[lo as usize] == c[hi as usize] {
            lo -= 1;
            hi += 1;
        }
        if hi - lo - 1 > best_hi - best_lo {                 // strictly longer
            best_lo = lo + 1;
            best_hi = hi;
        }
    }
    s[best_lo as usize..best_hi as usize].to_string()
}

import Data.List (foldl')

solve :: String -> String
solve s = take (hi - lo) (drop lo s)
  where
    n = length s
    at i = s !! i
    -- the widest palindrome around each centre, as (start, end)
    expand l h | l >= 0 && h < n && at l == at h = expand (l - 1) (h + 1)
               | otherwise = (l + 1, h)
    spans = [expand (c `div` 2) ((c + 1) `div` 2) | c <- [0 .. 2 * n - 2]]
    (lo, hi) = foldl' (\b@(bl, bh) x@(xl, xh) -> if xh - xl > bh - bl then x else b) (0, 1) spans

The same code is the reference solution to Longest palindromic substring, where it is compiled and run against the tests in all six languages.

TimeO(n²)

SpaceO(1) by expansion; O(n²) for the table

Manacher's algorithm finds it in O(n); it is rarely expected in an interview, but worth naming.