Last Updated: 4 Sep, 2022

Longest Palindromic Substring

Moderate

Asked in companies

Solve now

Problem statement

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.

Input Format

First-line contains 'T', denoting the number of Test cases.

For each Test case:

The first line contains an integer ‘N’ denoting the string ‘S’ length.
The second line contains the string ‘S’, consisting of lowercase English alphabets.

Output format :

Return the longest palindromic substring in ‘S’.

Note:-

You don't need to print anything. Just implement the given function.

Constraints :

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

Solve now

Approaches

01 Approach

The basic idea over here is to check for each possible substring of ‘S’ and verify whether it is a palindrome or not.

Pick all possible starting and ending positions, and check if it is a palindrome. If it is a palindrome, add one to the answer and finally return the answer after checking all substrings.

The steps are as follows:-

Initialise two integer variables, ‘start’ and ‘end’ with zero.
Run a loop from 'i' = 0... 'N' - 1:
- Again Run a loop from 'j' = 'i'... 'N' -1:
  - Update ‘start’ to ‘i’ and end to ‘j’, if the substring S[i:j] is a palindrome and its length is greater.
Return the substring ‘S[start: end]’ (including start and end).

Solve now

02 Approach

In the brute force solution, we do unnecessary recomputation for verifying palindromes. For example, if we know the string ‘dad’ is a palindrome, then ‘cdadc’ must be a palindrome as the left, and right characters are equal.

Hence we can store some information in a DP state to avoid this recomputation.

State- DP[i][j] = whether the substring S[i:j] is a palindrome or not.

Transition- DP[i][j] = DP[i-1][j-1] AND S[i] == S[j]

Base Cases:

One character DP[i][i]=True

Two character DP[i][i+1]= ( S[i] == S[i+1] )

The steps are as follows:-

Form a bottom-up DP 2D array. DP[i][j] will be ‘true’ if the index ‘i’ to ‘j’ string is a palindrome.
Run a loop from 'i' = 0... 'N' - 1:
- DP[i][i]=true ,since every string with one character is a palindrome.
Initialise two integer variables, ‘start’ and ‘end’ with zero.
Run a loop from 'i' = 0... 'N' - 1:
- Run a loop from 'j' = i+1... 'N' - 1:
  - If S[i] equals S[j] then :
    - If i+1 equals j, then DP[i][j] would be true.
    - Else DP[i][j] would be equal to DP[i-1][j-1]
    - If DP[i][j] is true and the previous length of the answer is less than (j-i+1), update ‘start’ to ‘i’ and end to ‘j’.
Return the substring ‘S[start: end]’ (including start and end).

Solve now