Problem of the day
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.
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.
1 <= 'T' <= 10
1 <= 'N' <= 10^5
‘a’ <= ‘S[i]’ <= ‘Z’
Time Limit: 1 sec
2
6
adccdb
6
aaabbb
dccd
aaa
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.
2
5
hello
1
a
ll
a
Try out all possible ways to buy and sell the stocks.
The basic idea over here is to check for each possible substring of ‘S’ and verify whether it is a palindrome or not.
Pick all possible starting and ending positions, and check if it is a palindrome. If it is a palindrome, add one to the answer and finally return the answer after checking all substrings.
The steps are as follows:-
O(N^3), where 'N' is the string ‘S’ length.
We have two nested loops of O(N) complexity each, and it takes O(N) to verify if it is a palindrome for each substring.
Hence the time complexity is O(N^3).
O(1).
We are using some variables that take some constant space.
Hence the space complexity is O(1).