Longest Symmetric Substring
MediumPractice library · +20 XPstringsdynamic programmingtwo pointers
Given a string S, find the longest substring of S which is also a palindrome. If there are multiple such substrings of the maximum length, return the one that appears first (leftmost starting index).
Input
A single string S.
Output
The longest palindromic substring.
Constraints
1 <= |S| <= 200000
Time limit 2 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
babad
Output
bab
The longest palindromic substrings are "bab" and "aba". "bab" starts earlier.
Example 2
Input
cbbd
Output
bb
The longest palindromic substring is "bb".
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
babad
Example 2 input
cbbd