PPractick

The problem

A text-mining tool looks for the longest contiguous stretch of a string that reads the same forwards and backwards, a feature used in DNA analysis (palindromic sequences mark biological sites) and in puzzle apps. Checking every substring is O(n³). The standard O(n²) method expands around each centre: every palindrome has a centre, either a single character (odd length) or the gap between two characters (even length), and from each centre you expand outwards while the ends match.

Example: "babad" → "bab" ("aba" is equally long; the leftmost is returned).

Function signature

string longestPalindrome(const string& s);  // leftmost longest palindromic substring

Test cases

Input s	Output	Explanation
"babad"	"bab"	"aba" ties; the leftmost wins
"cbbd"	"bb"	An even-length centre
"a"	"a"
"ac"	"a"	Every single character is a palindrome
"forgeeksskeegfor"	"geeksskeeg"
"racecar"	"racecar"	The whole string
"aaaa"	"aaaa"

(Confirm: return the leftmost palindrome among those of maximum length; the input is non-empty in the usual version, and an empty input returns an empty string.)

How interviewers phrase it

• "Find the longest palindromic substring" (LeetCode 5).
• Follow-ups: count all palindromic substrings (LeetCode 647), longest palindromic subsequence (a DP problem), Manacher's algorithm for O(n).

Clarifying questions to ask

1. Substring (contiguous) or subsequence?
2. If several have the same length, which one to return?
3. How long can the string be? (O(n²) is fine up to a few thousand; Manacher is O(n).)

Follow-ups to expect

1. "Why 2n − 1 centres?"
2. "What's the DP approach?"
3. "Can you do it in O(n)?"
4. "How would you count all palindromic substrings?"
5. "Complexity?"

Related questions

• Longest common subsequence Hard
• Print Longest Common Subsequence Hard
• Longest common substring Hard
• Longest palindromic subsequence Hard
• Minimum insertions to make string palindrome Hard
• Minimum insertions or deletions to convert string A to B Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in