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

Approach 1

- Generate substrings of the given string such that substring having greater length will be generated first.
- To do this, run a loop where iterator ‘LEN’ will go from N to 1, where N is the length of the given string.
- Run a nested loop and fix an iterator ‘j’ that will point at the starting index of the substring.
- Get the substring from ‘j’ to ‘j’ + ‘LEN’.
- If the substring is a palindrome, return the substring (as the substring will be of the longest length and minimum starting index).

Approach 2

- If the string length is less than or equal to 1 then return the string, as one length string is always palindromic.
- Initialize a ‘DP’ array of data type boolean, ‘DP’[i][j] will store false if STR[i, j] is not palindromic otherwise it will store true.
- Store all the diagonal elements (DP[i][i]) as true, as STR[i, i] will always be palindromic.
- For substring of length 2, check if STR[i] is equal to STR[i + 1] then store DP[i][i + 1] as true.
- Run a loop for the length of a substring greater than 2, fill the DP array diagonally.
- To calculate DP[i][j], check the value of DP[i + 1][j - 1], if the value is true and STR[i] is same as STR[j], then we make DP[i][j] true otherwise false.
- For every DP[i][j] true, update the length and starting index of the substring.

- Return the substring of the string having starting index as start and of maximum length.

Approach 3

- If the string length is less than or equal to 1 then return the string, as a single character is always palindromic.
- The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far. Run a loop where ‘i’ will be from 0 to ‘N’ - 1.
- To generate odd length palindrome, fix center ‘i’, and expand in both directions for longer palindromes. Odd length palindromes will have a character at the center.
- Similarly, for even length palindrome, fix the center as ‘i’, ‘i’ + 1, and expand in both directions. Even palindrome will have a partition between ith char and i+1th char as the center.
- If the length of the current palindromic substring length is greater then update the starting length of the string and length of the palindromic substring.

- Return the substring of the string having starting index as ‘START’ and of maximum length.

For expanding :

- For expanding around a center ‘i’ for odd length, initialize two variables ‘LEFT’ and ‘RIGHT’ to ‘i’ and go until ‘LEFT and ’RIGHT' are in range and STR[LEFT] == STR[RIGHT]. Decrement the ‘LEFT’ and increment the ‘RIGHT’.
- For expanding around a centre ‘i’ and ‘i’ + 1 for even length, initialise two variables ‘LEFT’ = ‘i’ and ‘RIGHT’ = ‘i’ + 1, and go until ‘LEFT’ and ‘RIGHT’ are in range and STR[LEFT] == STR[RIGHT]. Decrement the ‘LEFT’ and increment the ‘RIGHT’.
- Return the length of the palindromic substring.