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 substrings are of the same length.

Use dynamic programming to check for palindromes within the string.
Start by checking for palindromes of length 1 and 2, then expand to longer substrings.
Keep track of the longest palindromic substring found so far and return the rightmost one if multiple substrings are of the same length.

Top Software Developer Intern Interview Questions Asked at Goldman Sachs