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;
}