# Longest Palindromic Substring

Posted: 20 Sep, 2020

Difficulty: Easy

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