Longest Palindromic Substring solution and explanation
Cisco
9 more videos on this problem
Longest Palindromic Substring - Python - Leetcode 5NeetCode · 8:11 · 809K views
Longest palindromic substring | Dynamic programmingTechdose · 15:21 · 443K views
Longest Palindromic Substring Manacher's AlgorithmTushar Roy - Coding Made Simple · 16:46 · 406K views
LeetCode 5. Longest Palindromic Substring (Algorithm Explained)Nick White · 14:40 · 405K views
Longest Palindromic Sub-string (LeetCode 5) | Full solution with examples | Study AlgorithmsNikhil Lohia · 10:01 · 190K views
8. Longest Palindromic Substring | Leetcode 5 | Strings | Odd and even length approachAyushi Sharma · 16:27 · 109K views
Longest Palindromic Substring | LeetCode 5 | C++, Java, PythonKnowledge Center · 16:25 · 99K views
5. Longest Palindromic Substring | Day 001 | Brute - Better - Optimal | 2 Pointers | DPAryan Mittal · 21:14 · 65K views
LeetCode 5: Longest Palindromic SubstringAbstracted Away · 8:01 · 21K views
Longest palindrome substring - LeetCode Interview Coding Challenge [Java Brains]Java Brains · 20:57 · 125K views
The problem
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.
Approach overview
Problem Overview: Given a string s, return the longest substring that reads the same forward and backward. The substring must be contiguous, so you cannot rearrange characters or skip indices.
This problem sits at the intersection of string manipulation and palindrome detection. The challenge is checking all possible centers efficiently without recomputing the same substrings repeatedly.
Approach 1: Expand Around Center (Time: O(n2), Space: O(1))
A palindrome mirrors around its center. Every palindrome can have either one center (odd length like aba) or two centers (even length like abba). Iterate through the string and treat each index as a potential center. Expand outward using two pointers while the characters match.
For each index i, run two expansions: one with (i, i) for odd-length palindromes and another with (i, i+1) for even-length palindromes. Track the longest substring found during these expansions. Each expansion moves the two pointers outward until the characters differ or boundaries are reached.
This approach avoids storing intermediate states and checks only meaningful palindrome candidates. In the worst case (e.g., aaaaa) each expansion scans many characters, leading to O(n2) time, but the constant factors are small and memory usage stays O(1).
Approach 2: Dynamic Programming (Time: O(n2), Space: O(n2))
The dynamic programming approach builds a table dp[i][j] indicating whether substring s[i..j] is a palindrome. Single characters are palindromes, and pairs of equal characters form length-2 palindromes. For longer substrings, a substring is a palindrome if s[i] == s[j] and dp[i+1][j-1] is true.
Fill the DP table by increasing substring length. Each time a palindrome is confirmed, update the longest substring indices. This method ensures every substring is evaluated exactly once.
The main advantage is clarity: the palindrome property is expressed directly through subproblems. The downside is memory usage, since the DP table requires O(n2) space. For long strings this becomes expensive compared to the center-expansion approach.
Recommended for interviews: Expand Around Center is the solution most interviewers expect. It demonstrates understanding of palindrome symmetry and avoids unnecessary memory. Dynamic Programming shows strong problem decomposition but is rarely preferred due to its O(n2) space cost. Mentioning Manacher’s algorithm (O(n) time) can earn bonus points, though implementing it correctly during interviews is uncommon.
Approach 1: Expand Around Center
This approach is based on the observation that a palindrome mirrors around its center. Therefore, if we choose a center, we can expand outward to check for the longest possible palindrome. We can have centers between each two characters as well as on each character to cater for even and odd length palindromes.
class Solution:
def longestPalindrome(self, s: str) -> str:
def expandAroundCenter(s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
if not s:
return ""
start, end = 0, 0
for i in range(len(s)):
len1 = expandAroundCenter(s, i, i)
len2 = expandAroundCenter(s, i, i + 1)
length = max(len1, len2)
if length > end - start:
start = i - (length - 1) // 2
end = i + length // 2
return s[start:end + 1]class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}#include <string>
class Solution {
public:
std::string longestPalindrome(std::string s) {
if (s.empty()) return "";
int start = 0, end = 0;
for (int i = 0; i < s.size(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = std::max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substr(start, end - start + 1);
}
private:
int expandAroundCenter(const std::string &s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return right - left - 1;
}
};function longestPalindrome(s) {
if (!s || s.length < 1) return "";
let start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
let len1 = expandAroundCenter(s, i, i);
let len2 = expandAroundCenter(s, i, i + 1);
let len = Math.max(len1, len2);
if (len > end - start) {
start = i - Math.floor((len - 1) / 2);
end = i + Math.floor(len / 2);
}
}
return s.substring(start, end + 1);
}
function expandAroundCenter(s, left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return right - left - 1;
}#include <stdio.h>
#include <string.h>
int expandAroundCenter(char *s, int left, int right) {
while (left >= 0 && right < strlen(s) && s[left] == s[right]) {
left--;
right++;
}
return right - left - 1;
}
char * longestPalindrome(char * s){
if (s == NULL || strlen(s) < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < strlen(s); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = len1 > len2 ? len1 : len2;
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
char *result = (char *)malloc(end - start + 2);
strncpy(result, &s[start], end - start + 1);
result[end - start + 1] = '\0';
return result;
}public class Solution {
public string LongestPalindrome(string s) {
if (s == null || s.Length < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.Length; i++) {
int len1 = ExpandAroundCenter(s, i, i);
int len2 = ExpandAroundCenter(s, i, i + 1);
int len = Math.Max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.Substring(start, end - start + 1);
}
private int ExpandAroundCenter(string s, int left, int right) {
while (left >= 0 && right < s.Length && s[left] == s[right]) {
left--;
right++;
}
return right - left - 1;
}
}In this solution expansion is carried around potential palindrome centers. Given each character index, both single and dual element centers are employed, working out the longest span, which aids in building the final palindromic portion of the string.
Time Complexity: O(n^2) due to center expansions at all indices.
Space Complexity: O(1) disregarding output storage.
Approach 2: Dynamic Programming
In this approach, a 2D DP table is constructed where dp[i][j] is true if the string s[i...j] is a palindrome. Each entry is dependent on smaller substring checks. This method leverages overlapping subproblems.
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n == 0: return ""
dp = [[False] * n for _ in range(n)]
start, max_length = 0, 1
for i in range(n):
dp[i][i] = True
for begin in range(n - 1, -1, -1):
for end in range(begin + 1, n):
if s[begin] == s[end]:
if end - begin == 1 or dp[begin + 1][end - 1]:
dp[begin][end] = True
if end - begin + 1 > max_length:
start = begin
max_length = end - begin + 1
return s[start:start + max_length]class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n == 0) return "";
boolean[][] dp = new boolean[n][n];
int maxLength = 1;
int start = 0;
for (int i = 0; i < n; i++) dp[i][i] = true;
for (int begin = n - 1; begin >= 0; begin--) {
for (int end = begin + 1; end < n; end++) {
if (s.charAt(begin) == s.charAt(end)) {
if (end - begin == 1 || dp[begin + 1][end - 1]) {
dp[begin][end] = true;
if (end - begin + 1 > maxLength) {
start = begin;
maxLength = end - begin + 1;
}
}
}
}
}
return s.substring(start, start + maxLength);
}
}#include <string>
#include <vector>
class Solution {
public:
std::string longestPalindrome(std::string s) {
int n = s.size();
if (n == 0) return "";
std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
int start = 0, maxLength = 1;
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int begin = n - 1; begin >= 0; begin--) {
for (int end = begin + 1; end < n; end++) {
if (s[begin] == s[end]) {
if (end - begin == 1 || dp[begin + 1][end - 1]) {
dp[begin][end] = 1;
if (end - begin + 1 > maxLength) {
start = begin;
maxLength = end - begin + 1;
}
}
}
}
}
return s.substr(start, maxLength);
}
};function longestPalindrome(s) {
let n = s.length;
if (n === 0) return "";
let dp = Array.from(Array(n), () => Array(n).fill(false));
let start = 0;
let maxLength = 1;
for (let i = 0; i < n; i++) dp[i][i] = true;
for (let begin = n - 1; begin >= 0; begin--) {
for (let end = begin + 1; end < n; end++) {
if (s[begin] === s[end]) {
if (end - begin === 1 || dp[begin + 1][end - 1]) {
dp[begin][end] = true;
if (end - begin + 1 > maxLength) {
start = begin;
maxLength = end - begin + 1;
}
}
}
}
}
return s.substring(start, start + maxLength);
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *longestPalindrome(char *s) {
int n = strlen(s);
if (n == 0) return "";
int start = 0, maxLength = 1;
int **dp = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
dp[i] = (int *)malloc(n * sizeof(int));
memset(dp[i], 0, n * sizeof(int));
}
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int begin = n - 1; begin >= 0; begin--) {
for (int end = begin + 1; end < n; end++) {
if (s[begin] == s[end]) {
if (end - begin == 1 || dp[begin + 1][end - 1]) {
dp[begin][end] = 1;
if (end - begin + 1 > maxLength) {
start = begin;
maxLength = end - begin + 1;
}
}
}
}
}
char *result = (char *)malloc(maxLength + 1);
strncpy(result, s + start, maxLength);
result[maxLength] = '\0';
for (int i = 0; i < n; i++) free(dp[i]);
free(dp);
return result;
}public class Solution {
public string LongestPalindrome(string s) {
int n = s.Length;
if (n == 0) return "";
bool[,] dp = new bool[n, n];
int start = 0, maxLength = 1;
for (int i = 0; i < n; i++) dp[i, i] = true;
for (int begin = n - 1; begin >= 0; begin--) {
for (int end = begin + 1; end < n; end++) {
if (s[begin] == s[end]) {
if (end - begin == 1 || dp[begin + 1, end - 1]) {
dp[begin, end] = true;
if (end - begin + 1 > maxLength) {
start = begin;
maxLength = end - begin + 1;
}
}
}
}
}
return s.Substring(start, maxLength);
}
}Using Python, the DP strategy uses a list of lists capturing boolean statuses for substring palindromes, evaluating each with smaller pointers and checking towards determining max solutions.
Time Complexity: O(n^2) through overall DP table processing.
Space Complexity: O(n^2) due to memory required by the DP table for capturing boolean truths of substrings.
Approach 3: 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.
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);
}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]
}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()
}
}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]Approach 4: 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.
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]
}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();
}
}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;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Expand Around Center | Time Complexity: Space Complexity: |
| Dynamic Programming | Time Complexity: |
| Dynamic Programming | – |
| Enumerate Palindrome Midpoint | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Expand Around Center | O(n^2) | O(1) | Best general solution. Minimal memory and easy to implement in interviews. |
| Dynamic Programming | O(n^2) | O(n^2) | Useful when learning DP patterns or when substring states must be reused. |
| Manacher's Algorithm | O(n) | O(n) | Optimal theoretical solution. Rarely required in interviews due to implementation complexity. |
Frequently asked questions
Is Longest Palindromic Substring easy or hard?
Longest Palindromic Substring is classified as a Medium problem. The brute force idea is simple, but recognizing the center-expansion insight or building a correct DP table requires stronger string and algorithmic reasoning.
How to solve Longest Palindromic Substring in O(n)?
Manacher’s algorithm solves the problem in linear time by transforming the string and reusing previously computed palindrome radii. It avoids redundant comparisons by leveraging symmetry around known centers. The algorithm runs in O(n) time and O(n) space but is more complex than typical interview solutions.
Longest Palindromic Substring Python or Java solution?
Python and Java implementations usually follow the Expand Around Center technique. For each index, the algorithm expands outward for both odd and even centers and tracks the longest valid substring. This implementation runs in O(n^2) time with constant extra space.
What is the best approach for Longest Palindromic Substring?
Expand Around Center is the most practical approach. It checks palindromes by expanding two pointers outward from every possible center in the string. The algorithm runs in O(n^2) time and O(1) space while remaining simple enough to implement quickly during interviews.
Is Longest Palindromic Substring asked at Google/Amazon/Meta?
Longest Palindromic Substring frequently appears in technical interviews at large tech companies including Google, Amazon, Meta, and Microsoft. Interviewers typically expect the Expand Around Center solution and may discuss the tradeoffs between it and Dynamic Programming.
What data structure is used in Longest Palindromic Substring?
The problem mainly uses string traversal with two-pointer expansion. In the Dynamic Programming approach, a 2D boolean table stores whether substring s[i..j] is a palindrome. No advanced data structures are required for the optimal interview solution.
What is the time complexity of Longest Palindromic Substring?
Most standard solutions run in O(n^2) time. Expand Around Center checks up to 2n centers and expands outward, while Dynamic Programming evaluates every substring once. The optimal theoretical solution, Manacher’s algorithm, achieves O(n) time.