Longest Palindromic Substring

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
5 upvotes
Asked in companies
AmazonGoldman SachsOptum

Problem statement

Given a string ’S’ consisting of lower case English letters, you are supposed to return the longest palindromic substring of ‘S’.

Note that in case of more than one longest palindromic substrings with the same length you need to return the rightmost substring in the given string. For example in string “bbbab”, there are two possible longest palindromic substrings i.e. “bbb” and “bab”, and since you are supposed to return the rightmost substring, so you need to return “bab” as the answer.

Note: 
A substring is a contiguous sequence of elements within a string (for example, “bcd” is a substring of “abcde” while “bce” is not).

A string is said to be palindrome if the reverse of the string is the same as the actual string. For example, “abba” is a palindrome, but “abbc” is not a palindrome.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The only line of each test case contains a single string ‘S’ consisting of only lowercase English letters.
Output Format: 
For each test case, print a single string in a single line denoting the longest palindromic substring of string ‘S’.

The output for each test case is in a separate line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
1 <= N <= 100

Where ‘N’ is the length of the string.

Time limit: 1 sec
Sample Input 1:
2
abcbcbab
babbba
Sample Output 1:
abcbcba
abbba
Explanation of Sample Output 1:
In test case 1, the longest palindromic substring is “abcbcba”, which has a length of 7. Strings like “bcb” and “bcbcb” are also palindromic substrings of the given string, but not the longest one.

In test case 2, the longest palindromic substring is “abbba”, which has a length of 5. Substrings like “bab” and “bbb” are also palindromic substrings of the given string, but not the longest one.
Sample Input 2:
3
cbbd
bebeeeed
abcdad
Sample Output 2:
bb
eeee
dad
Explanation of Sample Output 2:
In test case 1, the longest palindromic substring is “bb”, which has a length of 2. Strings like “c”, “b” and “c” are also palindromic substrings of the given string, but not the longest one.

In test case 2, the longest palindromic substring is “eeee”, which has a length of 4. Substrings like “ebe” and “eee” are also palindromic substrings of the given string, but not the longest one.

In test case 3, the longest palindromic substring is “dad”, which has a length of 3. Substrings like “a”, “b”, “c”, and “d” are also palindromic substrings of the given string, but not the longest one.
Hint

Explore all the possible substrings and return the longest length of substring which are palindrome.

Approaches (3)
Brute Force

The brute force solution is to pick all possible starting and ending positions for a substring and verify if it is a palindrome.

 

The steps are as follows:

 

  1. If the length of the given string is zero, return an empty string. Else,
  2. Start checking each substring of the given string ‘S’ whether the substring is a palindrome or not.
  3. To do this first, run the two nested loops.
  4. These two loops pick up all the substrings one by one which can be done by fixing the corner characters.
  5. And inside the two loops, we are checking whether the picked substring is a palindrome or not.
  6. Now to check if the selected substring is palindrome or not, we are sending the starting and ending indexes of our selected substring in function isPalindrome() which returns ‘true’ if it’s a palindrome, otherwise, it returns ‘false’.
Time Complexity

O(N^3), Where ‘N’ is the length of the given string.

 

Since we are extracting all the substrings of the given string of length N accounting to the total N * (N - 1) / 2 substrings, now in order to verify if each of these substrings is a palindrome or not, it takes O(N) time, so the overall time complexity will be O(N ^ 3).

Space Complexity

O(1)

 

Since there is no extra space required, so the overall space complexity will be O(1).

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