 New update is available. Click here to update.
Last Updated: 18 Nov, 2020
##### Longest Palindromic Substring
Moderate
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.

##### 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.
``````
``````Try to solve it using O(1) space complexity.
``````
##### Constraints :
``````1 <= T <= 5
0 <= N <= 100

Time Limit: 1 sec
`````` Approaches

## 01Approach 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). 