Longest Palindromic Substring

Posted: 20 Sep, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given a string (STR) of length N.

Your task is to 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 starting index of "aba" 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 a single line containing the longest palindromic substring. 

If there are multiple possible answers then you need to print the substring which has the lowest starting index.
Note :
You do not need to 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 <= 10
0 <= N <= 10^3

where 'T' is the number of test cases, 'N' is the length of the given string.

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