Problem Statement:
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:
- Use Dynamic Programming (DP) to check if a
substring s[i...j]is a palindrome. - Maintain a
dp[i][j]table where:dp[i][j] = trueif substrings[i...j]is a palindrome.
- Base cases:
- Single character substrings
(dp[i][i] = true)are palindromes. - Two-character substrings
(s[i] == s[i+1])are palindromes.
- Single character substrings
- For substrings of
length ≥ 3:- A substring
s[i...j]is a palindrome ifs[i] == s[j]anddp[i+1][j-1]is true.
- A substring
- Track the longest palindrome’s start and end indices while filling DP
Return the longest palindromesubstring using substring (ans[0], ans[1] + 1).
Time & Space Complexity:
Time Complexity: O(n2)
Space Complexity: O(n2)
Dry Run
Input: s = "babad"
Step 0: Start Function longestPalindrome("babad")
n = 5
dp = 5x5 matrix filled with null
ans = [0, 0]
Base cases (length 1 and length 2 checks):
i = 0:
- dp[0][0] = true // "b"
- Check 2-length: s[0] === s[1]? "b" === "a" → false
State: ans = [0,0]
i = 1:
- dp[1][1] = true // "a"
- Check 2-length: s[1] === s[2]? "a" === "b" → false
State: ans = [0,0]
i = 2:
- dp[2][2] = true // "b"
- Check 2-length: s[2] === s[3]? "b" === "a" → false
State: ans = [0,0]
i = 3:
- dp[3][3] = true // "a"
- Check 2-length: s[3] === s[4]? "a" === "d" → false
State: ans = [0,0]
i = 4:
- dp[4][4] = true // "d"
- No i+1 to check
State: ans = [0,0]
Current dp (T = true, null = unset):
[
[T, null, null, null, null],
[ , T, null, null, null],
[ , , T, null, null],
[ , , , T, null],
[ , , , , T ]
]
Main loop (len = 3 ... n):
len = 3:
- i = 0, j = 2:
s[0] === s[2]? "b" === "b" → true
dp[1][1] is true → so dp[0][2] = true
ans = [0, 2] // substring "bab"
- i = 1, j = 3:
s[1] === s[3]? "a" === "a" → true
dp[2][2] is true → so dp[1][3] = true
ans = [1, 3] // substring "aba" (updates ans)
- i = 2, j = 4:
s[2] === s[4]? "b" === "d" → false
no update
dp now (noting newly true entries):
[
[T, null, T, null, null],
[ , T, null, T, null],
[ , , T, null, null],
[ , , , T, null],
[ , , , , T ]
]
len = 4:
- i = 0, j = 3:
s[0] === s[3]? "b" === "a" → false
- i = 1, j = 4:
s[1] === s[4]? "a" === "d" → false
(no changes)
len = 5:
- i = 0, j = 4:
s[0] === s[4]? "b" === "d" → false
(no changes)
Step 3: End
Final ans = [1, 3]
Return s.substring(1, 3 + 1) = "aba"
Output: "aba"
var longestPalindrome = function(s) {
let n = s.length;
if (n === 0) return "";
// dp[i][j] will be true if s[i..j] is a palindrome
let dp = Array.from({ length: n }, () => Array(n).fill(false));
let ans = [0, 0];
// Base cases: length 1 and length 2
for (let i = 0; i < n; i++) {
dp[i][i] = true; // single char
if (i < n - 1 && s[i] === s[i + 1]) {
dp[i][i + 1] = true;
ans = [i, i + 1];
}
}
// Check lengths from 3 to n
for (let len = 3; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
let j = i + len - 1;
if (s[i] === s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
ans = [i, j];
}
}
}
return s.substring(ans[0], ans[1] + 1);
};
def longest_palindrome(s: str) -> str:
n = len(s)
if n == 0:
return ""
dp = [[False] * n for _ in range(n)]
start, end = 0, 0
for i in range(n):
dp[i][i] = True
if i < n - 1 and s[i] == s[i + 1]:
dp[i][i + 1] = True
start, end = i, i + 1
for length in range(3, n + 1):
for i in range(0, n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
start, end = i, j
return s[start:end + 1]
public class Solution {
public static String longestPalindrome(String s) {
if (s == null || s.length() == 0) return "";
int n = s.length();
boolean[][] dp = new boolean[n][n];
int start = 0, end = 0;
for (int i = 0; i < n; i++) {
dp[i][i] = true;
if (i < n - 1 && s.charAt(i) == s.charAt(i + 1)) {
dp[i][i + 1] = true;
start = i; end = i + 1;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
dp[i][j] = true;
start = i; end = j;
}
}
}
return s.substring(start, end + 1);
}
}
#include <vector>
#include <string>
std::string longestPalindrome(const std::string &s) {
int n = (int)s.size();
if (n == 0) return "";
std::vector> dp(n, std::vector(n, 0));
int start = 0, end = 0;
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
if (i < n - 1 && s[i] == s[i + 1]) {
dp[i][i + 1] = 1;
start = i; end = i + 1;
}
}
for (int len = 3; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
if (s[i] == s[j] && dp[i + 1][j - 1]) {
dp[i][j] = 1;
start = i; end = j;
}
}
}
return s.substr(start, end - start + 1);
}
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
char* longestPalindrome(const char* s) {
if (!s) return strdup("");
int n = (int)strlen(s);
if (n == 0) return strdup("");
// Use a flat array for dp: dp[i*n + j]
unsigned char* dp = (unsigned char*)calloc((size_t)n * n, sizeof(unsigned char));
if (!dp) return strdup("");
int best_i = 0, best_j = 0;
// length 1 and 2
for (int i = 0; i < n; i++) {
dp[i * n + i] = 1;
if (i < n - 1 && s[i] == s[i + 1]) {
dp[i * n + (i + 1)] = 1;
best_i = i; best_j = i + 1;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s[i] == s[j] && dp[(i + 1) * n + (j - 1)]) {
dp[i * n + j] = 1;
best_i = i; best_j = j;
}
}
}
int outLen = best_j - best_i + 1;
char* res = (char*)malloc((size_t)outLen + 1);
if (res) {
memcpy(res, s + best_i, outLen);
res[outLen] = '\0';
}
free(dp);
return res;
}
using System;
public class Solution {
public static string LongestPalindrome(string s) {
int n = s?.Length ?? 0;
if (n == 0) return "";
bool[,] dp = new bool[n, n];
int start = 0, end = 0;
for (int i = 0; i < n; i++) {
dp[i, i] = true;
if (i < n - 1 && s[i] == s[i + 1]) {
dp[i, i + 1] = true;
start = i; end = i + 1;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s[i] == s[j] && dp[i + 1, j - 1]) {
dp[i, j] = true;
start = i; end = j;
}
}
}
return s.Substring(start, end - start + 1);
}
}
