Welcome to Subscribe On Youtube
5. Longest Palindromic Substring
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 <= 1000sconsist 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$.
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$.
-
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); } } -
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); } }; -
class Solution: def longestPalindrome(self, s: str) -> str: mlen = 0 start = end = 0 n = len(s) dp = [ [False] * n for i in range(n) ] for j in range(n): for i in range(j + 1): dp[i][j] = (i == j) or (s[i] == s[j] and j - i == 1) or (s[i] == s[j] and dp[i + 1][j - 1]) if dp[i][j] is True and j - i + 1 > mlen: mlen = j - i + 1 start = i end = j return s[start: end + 1] ###### 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] -
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] } -
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); } -
/** * @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); }; -
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); } } -
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] # Driver Code # echo(longestPalindrome("adbdaba")) -
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() } } -
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; } }