Longest Palindromic Substring

Given a string s, your task is to find and return the longest palindromic substring contained in s. A palindrome is a string that reads the same forwards and backwards. If there are multiple palindromic substrings with the maximum length, return the one that appears first in the string.

You can solve this problem using dynamic programming, or the expand-around-center approach. The optimal solution runs in O(n²) time complexity where n is the length of the string.

inputFormat

The input is provided via standard input (stdin) as a single line containing the string s.

outputFormat

The output should be written to standard output (stdout) as a single line containing the longest palindromic substring of the input string.

babad

bab