Two Pointers
String
Dynamic Programming
Description
Given a string s
, return the longest palindromic substring in s
.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Constraints:
1 <= s.length <= 1000
s
consist of only digits and English letters.
Solutions
Solution 1: Dynamic Programming
We define $f[i][j]$ to represent whether the string $s[i..j]$ is a palindrome, initially $f[i][j] = true$.
Next, we define variables $k$ and $mx$, where $k$ represents the starting position of the longest palindrome, and $mx$ represents the length of the longest palindrome. Initially, $k = 0$, $mx = 1$.
Considering $f[i][j]$, if $s[i] = s[j]$, then $f[i][j] = f[i + 1][j - 1]$; otherwise, $f[i][j] = false$. If $f[i][j] = true$ and $mx < j - i + 1$, then we update $k = i$, $mx = j - i + 1$.
Since $f[i][j]$ depends on $f[i + 1][j - 1]$, we need to ensure that $i + 1$ is before $j - 1$, so we need to enumerate $i$ from large to small, and enumerate $j$ from small to large.
The time complexity is $O(n^2)$, and the space complexity is $O(n^2)$. Here, $n$ is the length of the string $s$.
Python3 Java C++ Go TypeScript Rust JavaScript C# Nim
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def longestPalindrome ( self , s : str ) -> str :
n = len ( s )
f = [[ True ] * n for _ in range ( n )]
k , mx = 0 , 1
for i in range ( n - 2 , - 1 , - 1 ):
for j in range ( i + 1 , n ):
f [ i ][ j ] = False
if s [ i ] == s [ j ]:
f [ i ][ j ] = f [ i + 1 ][ j - 1 ]
if f [ i ][ j ] and mx < j - i + 1 :
k , mx = i , j - i + 1
return s [ k : k + mx ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public String longestPalindrome ( String s ) {
int n = s . length ();
boolean [][] f = new boolean [ n ][ n ] ;
for ( var g : f ) {
Arrays . fill ( g , true );
}
int k = 0 , mx = 1 ;
for ( int i = n - 2 ; i >= 0 ; -- i ) {
for ( int j = i + 1 ; j < n ; ++ j ) {
f [ i ][ j ] = false ;
if ( s . charAt ( i ) == s . charAt ( j )) {
f [ i ][ j ] = f [ i + 1 ][ j - 1 ] ;
if ( f [ i ][ j ] && mx < j - i + 1 ) {
mx = j - i + 1 ;
k = i ;
}
}
}
}
return s . substring ( k , k + mx );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public :
string longestPalindrome ( string s ) {
int n = s . size ();
vector < vector < bool >> f ( n , vector < bool > ( n , true ));
int k = 0 , mx = 1 ;
for ( int i = n - 2 ; ~ i ; -- i ) {
for ( int j = i + 1 ; j < n ; ++ j ) {
f [ i ][ j ] = false ;
if ( s [ i ] == s [ j ]) {
f [ i ][ j ] = f [ i + 1 ][ j - 1 ];
if ( f [ i ][ j ] && mx < j - i + 1 ) {
mx = j - i + 1 ;
k = i ;
}
}
}
}
return s . substr ( k , mx );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 func longestPalindrome ( s string ) string {
n := len ( s )
f := make ([][] bool , n )
for i := range f {
f [ i ] = make ([] bool , n )
for j := range f [ i ] {
f [ i ][ j ] = true
}
}
k , mx := 0 , 1
for i := n - 2 ; i >= 0 ; i -- {
for j := i + 1 ; j < n ; j ++ {
f [ i ][ j ] = false
if s [ i ] == s [ j ] {
f [ i ][ j ] = f [ i + 1 ][ j - 1 ]
if f [ i ][ j ] && mx < j - i + 1 {
mx = j - i + 1
k = i
}
}
}
}
return s [ k : k + mx ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 function longestPalindrome ( s : string ) : string {
const n = s . length ;
const f : boolean [][] = Array ( n )
. fill ( 0 )
. map (() => Array ( n ). fill ( true ));
let k = 0 ;
let mx = 1 ;
for ( let i = n - 2 ; i >= 0 ; -- i ) {
for ( let j = i + 1 ; j < n ; ++ j ) {
f [ i ][ j ] = false ;
if ( s [ i ] === s [ j ]) {
f [ i ][ j ] = f [ i + 1 ][ j - 1 ];
if ( f [ i ][ j ] && mx < j - i + 1 ) {
mx = j - i + 1 ;
k = i ;
}
}
}
}
return s . slice ( k , k + mx );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 impl Solution {
pub fn longest_palindrome ( s : String ) -> String {
let ( n , mut ans ) = ( s . len (), & s [ .. 1 ]);
let mut dp = vec! [ vec! [ false ; n ]; n ];
let data : Vec < char > = s . chars (). collect ();
for end in 1 .. n {
for start in 0 ..= end {
if data [ start ] == data [ end ] {
dp [ start ][ end ] = end - start < 2 || dp [ start + 1 ][ end - 1 ];
if dp [ start ][ end ] && end - start + 1 > ans . len () {
ans = & s [ start ..= end ];
}
}
}
}
ans . to_string ()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 /**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function ( s ) {
const n = s . length ;
const f = Array ( n )
. fill ( 0 )
. map (() => Array ( n ). fill ( true ));
let k = 0 ;
let mx = 1 ;
for ( let i = n - 2 ; i >= 0 ; -- i ) {
for ( let j = i + 1 ; j < n ; ++ j ) {
f [ i ][ j ] = false ;
if ( s [ i ] === s [ j ]) {
f [ i ][ j ] = f [ i + 1 ][ j - 1 ];
if ( f [ i ][ j ] && mx < j - i + 1 ) {
mx = j - i + 1 ;
k = i ;
}
}
}
}
return s . slice ( k , k + mx );
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 public class Solution {
public string LongestPalindrome ( string s ) {
int n = s . Length ;
bool [,] f = new bool [ n , n ];
for ( int i = 0 ; i < n ; i ++ ) {
for ( int j = 0 ; j < n ; ++ j ) {
f [ i , j ] = true ;
}
}
int k = 0 , mx = 1 ;
for ( int i = n - 2 ; i >= 0 ; -- i ) {
for ( int j = i + 1 ; j < n ; ++ j ) {
f [ i , j ] = false ;
if ( s [ i ] == s [ j ]) {
f [ i , j ] = f [ i + 1 , j - 1 ];
if ( f [ i , j ] && mx < j - i + 1 ) {
mx = j - i + 1 ;
k = i ;
}
}
}
}
return s . Substring ( k , mx );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 import std / sequtils
proc longestPalindrome ( s : string ): string =
let n : int = s . len ()
var
dp = newSeqWith [ bool ] ( n , newSeqWith [ bool ] ( n , false ))
start : int = 0
mx : int = 1
for j in 0 .. < n :
for i in 0 .. j :
if j - i < 2 :
dp [ i ][ j ] = s [ i ] == s [ j ]
else :
dp [ i ][ j ] = dp [ i + 1 ][ j - 1 ] and s [ i ] == s [ j ]
if dp [ i ][ j ] and mx < j - i + 1 :
start = i
mx = j - i + 1
result = s [ start .. < start + mx ]
Solution 2: Enumerate Palindrome Midpoint
We can enumerate the midpoint of the palindrome, spread to both sides, and find the longest palindrome.
The time complexity is $O(n^2)$, and the space complexity is $O(1)$. Here, $n$ is the length of the string $s$.
Python3 Java C++ Go Rust PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def longestPalindrome ( self , s : str ) -> str :
def f ( l , r ):
while l >= 0 and r < n and s [ l ] == s [ r ]:
l , r = l - 1 , r + 1
return r - l - 1
n = len ( s )
start , mx = 0 , 1
for i in range ( n ):
a = f ( i , i )
b = f ( i , i + 1 )
t = max ( a , b )
if mx < t :
mx = t
start = i - (( t - 1 ) >> 1 )
return s [ start : start + mx ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 class Solution {
private String s ;
private int n ;
public String longestPalindrome ( String s ) {
this . s = s ;
n = s . length ();
int start = 0 , mx = 1 ;
for ( int i = 0 ; i < n ; ++ i ) {
int a = f ( i , i );
int b = f ( i , i + 1 );
int t = Math . max ( a , b );
if ( mx < t ) {
mx = t ;
start = i - (( t - 1 ) >> 1 );
}
}
return s . substring ( start , start + mx );
}
private int f ( int l , int r ) {
while ( l >= 0 && r < n && s . charAt ( l ) == s . charAt ( r )) {
-- l ;
++ r ;
}
return r - l - 1 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public :
string longestPalindrome ( string s ) {
int n = s . size ();
int start = 0 , mx = 1 ;
auto f = [ & ]( int l , int r ) {
while ( l >= 0 && r < n && s [ l ] == s [ r ]) {
l -- , r ++ ;
}
return r - l - 1 ;
};
for ( int i = 0 ; i < n ; ++ i ) {
int a = f ( i , i );
int b = f ( i , i + 1 );
int t = max ( a , b );
if ( mx < t ) {
mx = t ;
start = i - ( t - 1 >> 1 );
}
}
return s . substr ( start , mx );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 func longestPalindrome ( s string ) string {
n := len ( s )
start , mx := 0 , 1
f := func ( l , r int ) int {
for l >= 0 && r < n && s [ l ] == s [ r ] {
l , r = l - 1 , r + 1
}
return r - l - 1
}
for i := range s {
a , b := f ( i , i ), f ( i , i + 1 )
t := max ( a , b )
if mx < t {
mx = t
start = i - (( t - 1 ) >> 1 )
}
}
return s [ start : start + mx ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 impl Solution {
pub fn is_palindrome ( s : & str ) -> bool {
let mut chars = s . chars ();
while let ( Some ( c1 ), Some ( c2 )) = ( chars . next (), chars . next_back ()) {
if c1 != c2 {
return false ;
}
}
true
}
pub fn longest_palindrome ( s : String ) -> String {
let size = s . len ();
let mut ans = & s [ .. 1 ];
for i in 0 .. size - 1 {
for j in ( i + 1 .. size ). rev () {
if ans . len () > j - i + 1 {
break ;
}
if Solution :: is_palindrome ( & s [ i ..= j ]) {
ans = & s [ i ..= j ];
}
}
}
return ans . to_string ();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 class Solution {
/**
* @param string $s
* @return string
*/
function longestPalindrome($s) {
$start = 0;
$maxLength = 0;
for ($i = 0; $i < strlen($s); $i++) {
$len1 = $this->expandFromCenter($s, $i, $i);
$len2 = $this->expandFromCenter($s, $i, $i + 1);
$len = max($len1, $len2);
if ($len > $maxLength) {
$start = $i - intval(($len - 1) / 2);
$maxLength = $len;
}
}
return substr($s, $start, $maxLength);
}
function expandFromCenter($s, $left, $right) {
while ($left >= 0 && $right < strlen($s) && $s[$left] === $s[$right]) {
$left--;
$right++;
}
return $right - $left - 1;
}
}