Problem

Submissions

Hints & solutions

Discuss

Longest Palindromic Substring

Moderate

0/80

Average time to solve is 20m

19 upvotes

Asked in companies

Problem statement

You are given a string ('STR') of length 'N'. Find the longest palindromic substring. If there is more than one palindromic substring with the maximum length, return the one with the smaller start index.

Note:

A substring is a contiguous segment of a string.

For example : The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome, there is another palindromic substring of length 3 is "bab" since "aba" starting index is less than "bab", so "aba" is the answer.

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

Input Format:

The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
Then the 'T' test cases follow.

The first and only one of each test case contains a string 'STR'.

Output Format :

For every test case, print the longest palindromic substring. 

If there are multiple possible answers then you need to print the substring which has the lowest starting index.

Note :

Do not print anything. It has already been taken care of. Just implement the given function.

Follow up:

Try to solve it using O(1) space complexity.

Constraints :

1 <= T <= 5
0 <= N <= 100

Time Limit: 1 sec

Sample Input 1:

1
abccbc

Sample Output 1:

bccb

Explanation for input 1:

For string "abccbc" there are multiple palindromic substrings like a,b,c,cc,bccb,cbc. But bccb is of longest length. Thus, answer is bccb.

Sample Input 2:

1
aeiou

Sample Output 2:

Explanation for input 2:

For string "aeiou" there are multiple palindromic substrings like a,e,i,o,u, and all of the same length. But "a" palindromic substring has the minimum starting index. Thus, answer is "a".

Hint 1

Hint 2

Hint 3

Hint 4

Think of brute force and try to generate all substring.

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Brute Force

Generate substrings of the given string such that substring having greater length will be generated first.
To do this, run a loop where iterator len will go from N to 1, where N is the length of the given string.
Run a nested loop and fix an iterator j that will point at the starting index of the substring.
Get the substring from j to j+len.
If the substring is a palindrome, return the substring (As the substring will be of the longest length and minimum starting index).

Time Complexity

O(N^3), where ‘N' is the length of string.

We are creating every substring which takes N^2 time. For checking whether the substring is palindromic takes O(length of substring) time, which can be maximum O(N). Thus, the total time complexity is O(N^3).

Space Complexity

O(N), where ‘N' is the length of the string

Here, as we are storing substring in a variable string.

(100% EXP penalty)

Longest Palindromic Substring

Console