Longest Palindromic Substring

Moderate

0/80

Average time to solve is 35m

Contributed by

1 upvote

+1 more companies

Problem statement

You are given a string ‘S’ of length ‘N’.

You must return the longest palindromic substring in ‘S’.

Note: Return any of them in case of multiple substrings with the same length.

Example:

Input: ‘S’ =’badam’

Output: ‘ada’

‘ada’ is the longest palindromic substring, and it can be proved that it is the longest possible palindromic substring.

Detailed explanation ( Input/output format, Notes, Images )

Input Format

First-line contains 'T', denoting the number of Test cases.

For each Test case:

The first line contains an integer ‘N’ denoting the string ‘S’ length.
The second line contains the string ‘S’, consisting of lowercase English alphabets.

Output format :

Return the longest palindromic substring in ‘S’.

Note:-

You don't need to print anything. Just implement the given function.

Constraints :

1 <= 'T' <= 10
1 <= 'N' <= 10^5
 ‘a’ <= ‘S[i]’ <= ‘Z’   
Time Limit: 1 sec

Sample Input 1 :

2
6
adccdb
6
aaabbb

Sample Output 1 :

dccd
aaa

Explanation Of Sample Input 1 :

For test case 1:

‘S’ =’adccdb’

‘dccd’ is the longest palindromic substring, and it can be proved that it is the longest possible palindromic substring.
Hence we return ‘dccd’.

For test case 2:

‘S’ =’aaabbb’

‘aaa’ is the longest palindromic substring, and it can be proved that it is the longest possible palindromic substring.
Hence we return ‘dccd’.
‘Bbb’ is also a valid answer.

Sample Input 2 :

2
5
hello
1
a

Sample Output 2 :

ll
a

Console