Longest Palindromic Substring

A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, civic, racecar, and aibohphobia (fear of palindromes).

Given a string $s$, find the longest palindromic substring in $s$. You may assume that the maximum length of $s$ is $1000$.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Let $p[i][j]$ be a table that states whether the substring $s_i\ldots s_j$ is a palindrome or not. Note that any substring of $length = 1$ can be considered as a palindrome. The following equation describes  the recurrence.

$p[i][j] = \begin{cases} true ,  & \text{if $l = 1$} \\[2ex] s_i == s_j,   & \text{if $l = 2$} \\[2ex] p[i+1][j-1]\; and \; s_i == s_j, & \text{if $len \gt 2$} \end{cases}$

Procedure LONGEST-PALINDROME-SUBSTRING takes a String as it’s input. It stores $p[i][j]$ values in a table $p[1 \ldots n][1 \ldots n]$ and it computes the entries in row-major order. 

 
**Input:** $s$ input string  
**Output:** the longest palindromic substring in $s$  
$LONGEST-PALINDROME-SUBSTRING(s)$  
$\phantom{{}++{}}$ $n \gets s.length$  
$\phantom{{}++{}}$ let $p[1 \ldots n][1 \ldots n]$ be a new table   
$\phantom{{}++{}}$ $start \gets 1$  
$\phantom{{}++{}}$ $l \gets 1$  
$\phantom{{}++{}}$  `for` $i = 1$ to $n$      
$\phantom{{}++{}}$$\phantom{{}++{}}$ $p[i][i] \gets true$  
$\phantom{{}++{}}$  `for` $i = 1$ to $n - 1$      
$\phantom{{}++{}}$$\phantom{{}++{}}$ $p[i][i + 1] \gets s_i == s_{i + 1}$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ `if` $p[i][i + 1]$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$  $l \gets 2$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $start \gets i$  
$\phantom{{}++{}}$  `for` $len = 3$ to $n$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ for $i = 1$ to $n - len + 1$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $j \gets i + len - 1$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $p[i][j] \gets s_i == s_j \; and\; p[i+1][j-1]$   
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ `if` $p[i][j]$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $l \gets len$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$  $start \gets i$  
$\phantom{{}++{}}$ return $s_{start} \ldots s_{start + l - 1}$

And here’s the code.

	class LongestPalindromicSubstring {
	LongestPalindromicSubstring() {
	throw new AssertionError();
	}
	public static void main(String[] args) {
	final String s = "babadbabad";
	final String p = longestPalindrome(s);
	System.out.println(p);
	}
	public static String longestPalindrome(String s) {
	final int n = s.length();
	final boolean[][] p = new boolean[n][n];
	int l = 1;
	int start = 0;
	for (int i = 0; i < n; i++)
	p[i][i] = true;
	for (int i = 0; i < n - 1; i++) {
	p[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
	if (p[i][i + 1]) {
	l = 2;
	start = i;
	}
	}
	for (int len = 3; len <= n; len++) {
	for (int i = 0; i < n - len + 1; i++) {
	final int j = i + len - 1;
	p[i][j] = s.charAt(i) == s.charAt(j) && p[i + 1][j - 1];
	if (p[i][j]) {
	start = i;
	l = len;
	}
	}
	}
	return s.substring(start, start + l);
	}
	}

view raw LongestPalindromicSubstr.java hosted with ❤ by GitHub

Analysis

Time complexity : $Θ(n^2)$
Space complexity: $Θ(n^2)$ to store the table.