Problem Statement:
Given a string s, find the longest palindromic substring in s. A palindrome is a string that reads the same forwards and backwards. You need to return the longest palindromic substring.
Example:
Example 1:
Input:s = "babad"
Output:"bab"
(Note: “aba” is also a valid answer.)
Example 2:
Input:s = "cbbd"
Output:"bb"
Approach:
We can solve this problem using Dynamic Programming (DP). The idea is to build a 2D table dp, where each entry dp[i][j] represents whether the substring s[i...j] is a palindrome. If dp[i][j] is True, it means that the substring s[i...j] is a palindrome.
The transitions are as follows:
- A single character is always a palindrome:
dp[i][i] = True. - Two adjacent characters are a palindrome if they are equal:
dp[i][i+1] = (s[i] == s[i+1]). - For substrings of length greater than 2,
s[i...j]is a palindrome ifs[i] == s[j]anddp[i+1][j-1]is also a palindrome.
Time Complexity:
- Time Complexity: O(n^2), where
nis the length of the string. This is because we fill the DP table, and each cell depends on the previous subproblem. - Space Complexity: O(n^2), due to the 2D DP table.
Algorithm:
- Create a 2D table
dpof sizen x nwherenis the length of the string. - Initialize all diagonal elements (
dp[i][i]) toTruebecause any single character is a palindrome. - For each substring of length 2 or more:
- If the substring has length 2, check if both characters are the same.
- For substrings longer than 2, check if the first and last characters are the same and if the inner substring is also a palindrome.
- Track the longest palindrome found during the process.
- Return the longest palindrome substring.
Code Implementation in Different Languages:
1. C:
#include <stdio.h>
#include <string.h>
char* longestPalindrome(char* s) {
int n = strlen(s);
if (n == 0) return "";
int dp[n][n];
memset(dp, 0, sizeof(dp));
int start = 0, maxLength = 1;
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (int length = 2; length <= n; length++) {
for (int i = 0; i < n - length + 1; i++) {
int j = i + length - 1;
if (s[i] == s[j] && (length == 2 || dp[i + 1][j - 1])) {
dp[i][j] = 1;
if (length > maxLength) {
start = i;
maxLength = length;
}
}
}
}
char* result = (char*)malloc((maxLength + 1) * sizeof(char));
strncpy(result, s + start, maxLength);
result[maxLength] = '\0';
return result;
}
int main() {
char s[] = "babad";
printf("Longest Palindromic Substring: %s\n", longestPalindrome(s));
return 0;
}
2. C++:
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
string longestPalindrome(string s) {
int n = s.length();
if (n == 0) return "";
vector<vector<bool>> dp(n, vector<bool>(n, false));
int start = 0, maxLength = 1;
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
for (int length = 2; length <= n; length++) {
for (int i = 0; i < n - length + 1; i++) {
int j = i + length - 1;
if (s[i] == s[j] && (length == 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (length > maxLength) {
start = i;
maxLength = length;
}
}
}
}
return s.substr(start, maxLength);
}
int main() {
string s = "babad";
cout << "Longest Palindromic Substring: " << longestPalindrome(s) << endl;
return 0;
}
3. Java:
public class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n == 0) return "";
boolean[][] dp = new boolean[n][n];
int start = 0, maxLength = 1;
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
for (int length = 2; length <= n; length++) {
for (int i = 0; i < n - length + 1; i++) {
int j = i + length - 1;
if (s.charAt(i) == s.charAt(j) && (length == 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (length > maxLength) {
start = i;
maxLength = length;
}
}
}
}
return s.substring(start, start + maxLength);
}
public static void main(String[] args) {
Solution sol = new Solution();
String s = "babad";
System.out.println("Longest Palindromic Substring: " + sol.longestPalindrome(s));
}
}
4. Python:
def longestPalindrome(s: str) -> str:
n = len(s)
if n == 0:
return ""
dp = [[False] * n for _ in range(n)]
start, maxLength = 0, 1
for i in range(n):
dp[i][i] = True
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and (length == 2 or dp[i + 1][j - 1]):
dp[i][j] = True
if length > maxLength:
start = i
maxLength = length
return s[start:start + maxLength]
# Test
s = "babad"
print("Longest Palindromic Substring:", longestPalindrome(s))
5. C#:
using System;
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 length = 2; length <= n; length++) {
for (int i = 0; i < n - length + 1; i++) {
int j = i + length - 1;
if (s[i] == s[j] && (length == 2 || dp[i + 1, j - 1])) {
dp[i, j] = true;
if (length > maxLength) {
start = i;
maxLength = length;
}
}
}
}
return s.Substring(start, maxLength);
}
public static void Main(string[] args) {
Solution sol = new Solution();
string s = "babad";
Console.WriteLine("Longest Palindromic Substring: " + sol.LongestPalindrome(s));
}
}
6. JavaScript:
var longestPalindrome = function(s) {
const n = s.length;
if (n === 0) return "";
const dp = Array.from({ length: n }, () => Array(n).fill(false));
let start = 0, maxLength = 1;
for (let i = 0; i < n; i++) {
dp[i][i] = true;
}
for (let length = 2; length <= n; length++) {
for (let i = 0; i < n - length + 1; i++) {
const j = i + length - 1;
if (s[i] === s[j] && (length === 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (length > maxLength) {
start = i;
maxLength = length;
}
}
}
}
return s.substring(start, start + maxLength);
};
// Test
let s = "babad";
console.log("Longest Palindromic Substring:", longestPalindrome(s));
Summary:
- Time Complexity: O(n²), where
nis the length of the input string. This is due to the nested loops filling the DP table. - Space Complexity: O(n²), because we store results for all substring pairs in the DP table.