Longest Palindromic Substring

Longest Palindromic Substring

What is this problem about?

The Longest Palindromic Substring interview question gives you a string s and asks you to find the longest contiguous sequence of characters that reads the same forwards and backwards. For instance, in the string "babad", the longest palindromic substring is "bab" (or "aba", which is equally valid).

Why is this asked in interviews?

This is one of the most famous string problems in tech interviews. It tests a candidate's ability to recognize that brute-forcing all substrings takes $O(N^3)$ time, which is unacceptable. Interviewers want to see if you can optimize the search to $O(N^2)$ using the "Expand Around Center" technique or Dynamic Programming. It is a fantastic benchmark for identifying clean, off-by-one-free coding skills.

Algorithmic pattern used

The most practical and intuitive approach is the Two Pointers (Expand Around Center) pattern. Because a palindrome mirrors around its center, there are $2N - 1$ possible centers in a string of length $N$ (a center can be a single character, or the space between two characters). You iterate through every possible center and use two pointers to expand outwards as long as the characters match.

Example explanation

Consider the string "cbbd". We iterate through centers:

• Center at index 0 ('c'): Expands to "c". Length 1.
• Center between 0 and 1: 'c' != 'b'. Length 0.
• Center at index 1 ('b'): Expands outwards. Left to 0 ('c'), Right to 2 ('b'). 'c' != 'b'. It stops. Palindrome is "b". Length 1.
• Center between 1 and 2: 'b' == 'b'. Expands! Left to 0 ('c'), Right to 3 ('d'). 'c' != 'd'. Palindrome is "bb". Length 2.
• Center at index 2 ('b'): Expands outwards. Left to 1 ('b'), Right to 3 ('d'). 'b' != 'd'. It stops. Length 1. The longest we found was "bb".

Common mistakes candidates make

A very common mistake is forgetting that palindromes can have an even length (like "abba"). If candidates only write logic to expand from a single character, they will completely miss all even-length palindromes. You must explicitly handle both the single-character center expand(i, i) and the two-character center expand(i, i+1).

Interview preparation tip

To ace the Longest Palindromic Substring coding problem, memorize the "Expand Around Center" helper function. It is much more space-efficient ($O(1)$ space) than the 2D Dynamic Programming solution ($O(N^2)$ space) and easier to write under pressure. Keep your bounds checking clean: while left >= 0 and right < len(s) and s[left] == s[right].