Longest Palindromic Substring

Posted: 18 Nov, 2020
Difficulty: Moderate


Try Problem

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.

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.

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
Approach 1
  1. Generate substrings of the given string such that substring having greater length will be generated first.
  2. To do this, run a loop where iterator len will go from N to 1, where N is the length of the given string.
  3. Run a nested loop and fix an iterator j that will point at the starting index of the substring.
  4. Get the substring from j to j+len.
  5. If the substring is a palindrome, return the substring (As the substring will be of the longest length and minimum starting index).
Try Problem