New update is available. Click here to update.

Topics

You are given a string ‘S’ of length ‘N’.

You must return the longest palindromic substring in ‘S’.

Note: Return any of them in case of multiple substrings with the same length.

Example:

```
Input: ‘S’ =’badam’
Output: ‘ada’
‘ada’ is the longest palindromic substring, and it can be proved that it is the longest possible palindromic substring.
```

Detailed explanation

```
1 <= 'T' <= 10
1 <= 'N' <= 10^5
‘a’ <= ‘S[i]’ <= ‘Z’
Time Limit: 1 sec
```

```
2
6
adccdb
6
aaabbb
```

```
dccd
aaa
```

```
For test case 1:
‘S’ =’adccdb’
‘dccd’ is the longest palindromic substring, and it can be proved that it is the longest possible palindromic substring.
Hence we return ‘dccd’.
For test case 2:
‘S’ =’aaabbb’
‘aaa’ is the longest palindromic substring, and it can be proved that it is the longest possible palindromic substring.
Hence we return ‘dccd’.
‘Bbb’ is also a valid answer.
```

```
2
5
hello
1
a
```

```
ll
a
```