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.

Analysis

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

Comments

Popular posts from this blog

Introducing Java Reactive Extentions in to a SpringBoot Micro Service

Optimal binary search trees

Combining the emissions of multiple Observables together using RxJava Zip operator in a Spring Boot Micro service