Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Longest Palindromic Substring

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
3 upvotes
Asked in companies
Paytm (One97 Communications Limited)MicrosoftAmazon

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 )
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
Full screen
Console