Longest Palindromic Substring

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

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
Hint

Try out all possible ways to buy and sell the stocks.

Approaches (2)
Brute force

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:-

 

  1. Initialise two integer variables, ‘start’ and ‘end’ with zero.
  2. Run a loop from 'i' = 0... 'N' - 1:
    • Again Run a loop from 'j' = 'i'... 'N' -1:
      • Update ‘start’ to ‘i’ and end to ‘j’, if the substring S[i:j] is a palindrome and its length is greater.
  3. Return the substring ‘S[start: end]’ (including start and end).
Time Complexity

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).

Space Complexity

O(1).

 

We are using some variables that take some constant space.  

 

Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Longest Palindromic Substring
Full screen
Console