Longest Palindromic Substring
Given a string ’S’ consisting of lower case English letters, you are supposed to return the longest palindromic substring of ‘S’.

Note that in case of more than one longest palindromic substrings with the same length you need to return the rightmost substring in the given string. For example in string “bbbab”, there are two possible longest palindromic substrings i.e. “bbb” and “bab”, and since you are supposed to return the rightmost substring, so you need to return “bab” as the answer.

Note:

A substring is a contiguous sequence of elements within a string (for example, “bcd” is a substring of “abcde” while “bce” is not). A string is said to be palindrome if the reverse of the string is the same as the actual string. For example, “abba” is a palindrome, but “abbc” is not a palindrome.

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow. The only line of each test case contains a single string ‘S’ consisting of only lowercase English letters.

Output Format:

For each test case, print a single string in a single line denoting the longest palindromic substring of string ‘S’. The output for each test case is in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Longest Palindromic Substring

Given a string ’S’ consisting of lower case English letters, you are supposed to return the longest palindromic substring of ‘S’.

Note that in case of more than one longest palindromic substrings with the same length you need to return the rightmost substring in the given string. For example in string “bbbab”, there are two possible longest palindromic substrings i.e. “bbb” and “bab”, and since you are supposed to return the rightmost substring, so you need to return “bab” as the answer.

Note:

A substring is a contiguous sequence of elements within a string (for example, “bcd” is a substring of “abcde” while “bce” is not).

A string is said to be palindrome if the reverse of the string is the same as the actual string. For example, “abba” is a palindrome, but “abbc” is not a palindrome.

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The only line of each test case contains a single string ‘S’ consisting of only lowercase English letters.

Output Format:

For each test case, print a single string in a single line denoting the longest palindromic substring of string ‘S’.

The output for each test case is in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 100

Where ‘N’ is the length of the string.

Time limit: 1 sec

Accepted Answer

Approach :

1) Create a 2-D dp boolean vector(with all false initially) where dp[i][j] states whether s[i...j] is a palindrome or not and initilialise a variable ans=1 which will store the final answer.

2) Base Case : For every i from 0 to n-1 fill dp[i][i]=1 ( as a single character is always a palindrome ).

3) Now, run 2 loops first one from i=n-1 to i=0 (i.e., tarverse from the back of the string) and the second one from j=i+1 to n.

4) For every s[i]==s[j] , check if(j-i==1 i.e., if s[i] and s[ j] are two consecutive same letters) or if(dp[i+1][j-1]==1 or not i.e., if the string s[i+1,....j-1] is palindrome or not.

5) Because if the string s[i+1,....j-1] is a palindrome and s[i]==s[j] then s[i] and s[j] can be appended at the starting and the ending position of s[i+1,...j-1] and s[i...j] will then be a palindrome , so mark dp[i][j]=1 and update the answer as ans=max(ans , j-i+1).

6) Finally return the ans

TC : O(N^2) where N=length of the string s
SC : O(N^2)

Accepted Answer

Brute Force

The brute force solution is to pick all possible starting and ending positions for a substring and verify if it is a palindrome.

The steps are as follows:

If the length of the given string is zero, return an empty string. Else,
Start checking each substring of the given string ‘S’ whether the substring is a palindrome or not.
To do this first, run the two nested loops.
These two loops pick up all the substrings one by one which can be done by fixing the corner characters.
And inside the two loops, we are checking whether the picked substring is a palindrome or not.
Now to check if the selected substring is palindrome or not, we are sending the starting and ending indexes of our selected substring in function isPalindrome() which returns ‘true’ if it’s a palindrome, otherwise, it returns ‘false’.

Space Complexity: O(1)Explanation:

O(1)

Since there is no extra space required, so the overall space complexity will be O(1).

Time Complexity: O(n^3)Explanation:

O(N^3), Where ‘N’ is the length of the given string.

Since we are extracting all the substrings of the given string of length N accounting to the total N * (N - 1) / 2 substrings, now in order to verify if each of these substrings is a palindrome or not, it takes O(N) time, so the overall time complexity will be O(N ^ 3).

Accepted Answer

Dynamic Programming

To improve our brute force solution, we first observe how we can avoid unnecessary re-computation while we are validating if a substring is a palindrome or not. Consider the case "xyzyx". Assume if we already know that "yzy" is a palindrome, then it seems obvious that "xyzyx" must be a palindrome since the two left and right end letters are the same.

The time complexity can be reduced by storing the prior results of its subproblems.

The steps are as follows:

If the length of the given string is zero, then return an empty string. Else,
Now we make a boolean ‘DP[N][N]’ for storing the result of each substring, where ‘N’ is the length of the given string ‘S’.
Any element in the ‘DP’ matrix, say ‘DP[i][j]’ represents whether a substring starting from ‘i’th index and ending at the ‘j’th index of the given string is a palindrome or not. The value of ‘DP[i][j]’ is “true” if the substring is a palindrome, otherwise “false”.
To calculate ‘DP[i][j]’, we check the value of ‘DP[i + 1][j - 1]’, if the value is “true” and ‘S[i]’ is the same as ‘S[j]’, then we make ‘DP[i][j]’ “true”.
Else, the value of ‘DP[i][j]’ is made “false”.
Prior to the computations of a substring with length greater than 2, we have to fill ‘DP’ matrix for a substring of length one and two because sometimes for corner positions (i+1) and (j-1) doesn’t exist between [0, ‘N’ - 1] range of the given string.

Space Complexity: O(n^2)Explanation:

O(N ^ 2), Where ‘N’ is the length of the given string.

Since Matrix DP of size N x N is needed to store the DP implementation, so the overall space complexity will be O(N ^ 2).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), Where ‘N’ is the length of the given string.

Since we are extracting all the substrings of the given string accounting to total N * (N - 1) / 2 substrings, so the overall time complexity will be O(N ^ 2).

Accepted Answer

Expand Around The Centre

When you observe closely you will realise that a palindrome has mirrors around its centre, a palindrome can be expanded in both directions from its centre.

The steps are as follows:

If the length of the given string is zero, then return an empty string. Else,
Considering the mirror phenomenon there are 2 * ‘N’ - 1 such centre that we need to consider.
Now you might be wondering why there are 2 * ‘N’ - 1 but not ‘N’ centres? The reason is that the centre of a palindrome can be in between two letters of the given string as well.
there are ‘N’ - 1 space in the given string of length ‘N’ from which an even length palindrome can be computed
while the palindromes originating with each element of the given string constitute ‘N’ possibilities of an odd length palindrome.

For example, in a string “abbab” of length 5, there are 5 possibilities that a palindrome can originate from the 5 indexes, so there are 5 substrings: “a”, “b”, “b”, “bab”, and “b” respectively (These are the longest palindromic substrings possible originating from each index of the string). All these accounts for an odd length palindrome.

Now, what about even length palindromes? Since there are 4 spaces in between the 5 characters of the given string, so the longest palindromic substrings possible originating from each space of the given string are “”, “abba”, “”, and “” respectively.

Now out of all these 9 possibilities, the longest palindromic substring is “abba”.

We keep on expanding the palindrome considering these centres as the centre of each substring, and simultaneously we keep on validating if the substring originating from each centre is a palindrome or not.

Space Complexity: O(1)Explanation:

O(1)

Since there is no extra space required, so the overall space complexity will be O(1).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), Where ‘N’ is the length of the given string.

Since the expanding of a palindrome around its centre can take O(N) time and there would be at most (2 * ‘N’ - 1) centres, so the overall time complexity will be O(N ^ 2).

Given a string ’S’ consisting of lower case English letters, you are supposed to return the longest palindromic substring of ‘S’.

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Nagarro Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Nagarro Software Developer