New update is available. Click here to update.

# 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.
``````1 <= T <= 10