Problem Statement
Given a string s, find the longest palindromic substring in s. A palindrome is a sequence of characters that reads the same backward as forward. Your task is to return the longest substring of s that is a palindrome.
Example
Input:s = "babad"
Output:"bab" or "aba" (both are valid)
Explanation:
The string contains multiple palindromic substrings such as “bab”, “aba”, and “a”. The longest one is either “bab” or “aba”.
Approach
1. Expand Around Center
- Every palindrome is mirrored around its center. For each character in the string, expand outward while the characters match.
- Consider both single characters and pairs of characters as the center.
2. Dynamic Programming
- Use a 2D table where
dp[i][j]istrueif the substrings[i...j]is a palindrome. - Fill the table based on smaller substrings first and then larger substrings.
3. Brute Force
- Generate all substrings of
sand check each one to see if it’s a palindrome. Keep track of the longest one.
Algorithm
Expand Around Center
- Initialize variables for tracking the start and length of the longest palindrome.
- Iterate through each character in the string, treating it as the center of the palindrome.
- For each center, expand outward in both directions while the characters match.
- Update the longest palindrome if a larger one is found.
- Return the substring corresponding to the longest palindrome.
Complexity
- Time Complexity: O(n2)O(n^2)O(n2) for expanding around each center.
- Space Complexity: O(1)O(1)O(1), as no additional data structures are used.
Implementation
C
#include <stdio.h>
#include <string.h>
char* longestPalindrome(char* s) {
int start = 0, maxLength = 0;
int len = strlen(s);
for (int i = 0; i < len; i++) {
int l = i, r = i;
while (l >= 0 && r < len && s[l] == s[r]) {
if (r - l + 1 > maxLength) {
start = l;
maxLength = r - l + 1;
}
l--;
r++;
}
l = i;
r = i + 1;
while (l >= 0 && r < len && s[l] == s[r]) {
if (r - l + 1 > maxLength) {
start = l;
maxLength = r - l + 1;
}
l--;
r++;
}
}
s[start + maxLength] = '\0';
return s + start;
}
int main() {
char s[] = "babad";
printf("Longest Palindromic Substring: %s\n", longestPalindrome(s));
return 0;
}
C++
#include <iostream>
#include <string>
using namespace std;
string longestPalindrome(string s) {
int start = 0, maxLength = 0, n = s.length();
for (int i = 0; i < n; i++) {
int l = i, r = i;
while (l >= 0 && r < n && s[l] == s[r]) {
if (r - l + 1 > maxLength) {
start = l;
maxLength = r - l + 1;
}
l--; r++;
}
l = i, r = i + 1;
while (l >= 0 && r < n && s[l] == s[r]) {
if (r - l + 1 > maxLength) {
start = l;
maxLength = r - l + 1;
}
l--; r++;
}
}
return s.substr(start, maxLength);
}
int main() {
string s = "babad";
cout << "Longest Palindromic Substring: " << longestPalindrome(s) << endl;
return 0;
}
Java
public class LongestPalindromicSubstring {
public static String longestPalindrome(String s) {
int start = 0, maxLength = 0;
for (int i = 0; i < s.length(); i++) {
int l = i, r = i;
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
if (r - l + 1 > maxLength) {
start = l;
maxLength = r - l + 1;
}
l--; r++;
}
l = i;
r = i + 1;
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
if (r - l + 1 > maxLength) {
start = l;
maxLength = r - l + 1;
}
l--; r++;
}
}
return s.substring(start, start + maxLength);
}
public static void main(String[] args) {
String s = "babad";
System.out.println("Longest Palindromic Substring: " + longestPalindrome(s));
}
}
Python
def longest_palindrome(s: str) -> str:
start, max_length = 0, 0
for i in range(len(s)):
l, r = i, i
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > max_length:
start, max_length = l, r - l + 1
l -= 1
r += 1
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > max_length:
start, max_length = l, r - l + 1
l -= 1
r += 1
return s[start:start + max_length]
# Example usage
print("Longest Palindromic Substring:", longest_palindrome("babad"))
C#
using System;
class LongestPalindromicSubstring {
public static string LongestPalindrome(string s) {
int start = 0, maxLength = 0;
for (int i = 0; i < s.Length; i++) {
int l = i, r = i;
while (l >= 0 && r < s.Length && s[l] == s[r]) {
if (r - l + 1 > maxLength) {
start = l;
maxLength = r - l + 1;
}
l--; r++;
}
l = i; r = i + 1;
while (l >= 0 && r < s.Length && s[l] == s[r]) {
if (r - l + 1 > maxLength) {
start = l;
maxLength = r - l + 1;
}
l--; r++;
}
}
return s.Substring(start, maxLength);
}
static void Main() {
string s = "babad";
Console.WriteLine("Longest Palindromic Substring: " + LongestPalindrome(s));
}
}
JavaScript
function longestPalindrome(s) {
let start = 0, maxLength = 0;
for (let i = 0; i < s.length; i++) {
let l = i, r = i;
while (l >= 0 && r < s.length && s[l] === s[r]) {
if (r - l + 1 > maxLength) {
start = l;
maxLength = r - l + 1;
}
l--; r++;
}
l = i; r = i + 1;
while (l >= 0 && r < s.length && s[l] === s[r]) {
if (r - l + 1 > maxLength) {
start = l;
maxLength = r - l + 1;
}
l--; r++;
}
}
return s.substring(start, start + maxLength);
}
console.log("Longest Palindromic Substring:", longestPalindrome("babad"));