Problem 42: Longest Palindromic Substring
Problem Statement: Given a string, find the longest substring which is a palindrome. If there are multiple answers, print any one of them.
Input
A single line containing the string.
Output
Print the longest palindromic substring.
Examples
Input:
babad
Output:
bab
Solution Explanation
Method 1: Expand around each possible center (each index and between indices) to find all palindromic substrings and track the longest. Method 2: Use dynamic programming to precompute a 2D table that determines if a substring is a palindrome, then extract the longest true entry.
Solution in C++
#include
#include
#include
using namespace std;
string longestPalindrome(string s) {
int n = s.size();
if (n == 0) return "";
int start = 0, maxLen = 1;
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 > maxLen){
start = l;
maxLen = r - l + 1;
}
l--; r++;
}
l = i, r = i+1;
while(l >= 0 && r < n && s[l] == s[r]){
if(r - l + 1 > maxLen){
start = l;
maxLen = r - l + 1;
}
l--; r++;
}
}
return s.substr(start, maxLen);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s; cin >> s;
cout << longestPalindrome(s) << "
";
return 0;
}