Longest Palindromic Substring
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

Question

Longest Palindromic Substring

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

Accepted Answer

Step 1 : I first thought of the naive approach by first considering all the substrings and then check weather it is a palindrome or not and then check weather its length is maximum till now or not. But the complexity of this approach was O(n^3) which can't be executed according to constraints.
Step 2 : Then I thought of another DP approach using gap strategy of first finding palindrome for small length substrings and then use the answer to calculate further.
The complexity of this approach was O(n^2) and I was able to pass all the test cases.

Accepted Answer

Brute Force

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).

Space Complexity: O(n)Explanation:

O(N), where N is the length of the given string.

We are storing substring in a variable string.

Time Complexity: O(n^3)Explanation:

O(N ^ 3), where N is the length of the given string.

We are creating every substring which takes N ^ 2 time. Checking whether the substring is palindromic takes O(length of substring) time, which can be maximum O(N). Thus, the total time complexity is O(N ^ 3).

Accepted Answer

Dynamic Programming

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.
1. 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.
2. 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.

Space Complexity: O(n^2)Explanation:

O(N ^ 2), where N is the length of the given string.

We are using a ‘DP’ array of N*N dimensions.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where N is the length of the given string as

We are traversing the ‘DP’ array once.

Accepted Answer

Expanding around the centres

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.
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.
2. 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.
3. 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.

Space Complexity: O(1)Explanation:

O(1).

As we are not using any extra space.