# Longest Palindromic Substring

Posted: 20 Sep, 2020
Difficulty: Easy

## PROBLEM STATEMENT

#### 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.
``````

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