Find the Longest Palindromic Substring

Given a string ‘S’ composed of lowercase English letters, your task is to identify the longest palindromic substring within ‘S’.

If there are multiple longest palindromic substrings of the same length, return the rightmost one in the given string.

Example:

Input:

bbbab

Output:

bab

Explanation:

In the string “bbbab”, there are two longest palindromic substrings of equal length: “bbb” and “bab”. The rightmost one, “bab”, should be returned.

Constraints:

1

Question

Given a string ‘S’ composed of lowercase English letters, your task is to identify the longest palindromic substring within ‘S’.

If there are multiple longest palindromic substrings of the same length, return the rightmost one in the given string.

bbbab

bab

In the string “bbbab”, there are two longest palindromic substrings of equal length: “bbb” and “bab”. The rightmost one, “bab”, should be returned.

Where ‘N’ is the length of the string.

A substring is a contiguous sequence of characters within a string. A string is a palindrome if it reads the same forwards and backwards.

You do not need to print anything; this has been handled. Implement the function to return the desired result.

Accepted Answer

Find the longest palindromic substring in a given string, returning the rightmost one if multiple exist.

Use dynamic programming to check if substrings are palindromes
Iterate through the string and expand around each character to find palindromic substrings
Keep track of the longest palindromic substring found

TCS iON Software Developer interview questions & answers