LeetCode 0005. Longest Palindromic Substring Solution in Java, C++, Python & More | Explanation + Code

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.

PythonJavaC++GoTypeScriptRustJavaScriptC#CNim

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](code-box)

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); } }(code-box)

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); } };(code-box)

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] }(code-box)

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); }(code-box)

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() } }(code-box)

/** * @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); };(code-box)

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); } }(code-box)

char* longestPalindrome(char* s) { int n = strlen(s); bool** f = (bool**) malloc(n * sizeof(bool*)); for (int i = 0; i < n; ++i) { f[i] = (bool*) malloc(n * sizeof(bool)); for (int j = 0; j < n; ++j) { f[i][j] = 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; } } } } char* res = (char*) malloc((mx + 1) * sizeof(char)); strncpy(res, s + k, mx); res[mx] = '\0'; for (int i = 0; i < n; ++i) { free(f[i]); } free(f); return res; }(code-box)

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](code-box)

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.

PythonJavaC++GoRustC#PHP

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](code-box)

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; } }(code-box)

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); } };(code-box)

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] }(code-box)

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(); } }(code-box)

public 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[l] == s[r]) { --l; ++r; } return r - l - 1; } }(code-box)

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; } }(code-box)