How do you approach Longest Palindromic Substring?

A palindrome mirrors around its center.

What is the time complexity of Longest Palindromic Substring?

Time complexity: O(n²). Space complexity: O(1).

What are common mistakes on Longest Palindromic Substring?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Longest Palindromic Substring

MediumAlgorithms

Description

Given a string s, return the longest palindromic substring in s.

Example 1

Input: s = "babad"

Output: "bab"

Explanation: "aba" is also a valid answer.

Example 2

Input: s = "cbbd"

Output: "bb"

Constraints

- 1 <= s.length <= 1000 - s consist of only digits and English letters.

Longest Palindromic Substring: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 6 test cases (3 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 3-step hint ladder

A palindrome mirrors around its center.
There are 2n-1 possible centers (between characters or on characters).
Expand around each center and track the longest palindrome found.

The optimal approach

Show the approach: Expand Around Center

For each possible center (character or between characters), expand outward while the characters match. Track the longest palindrome found.

Time: O(n²)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.