Coding interview problems › Dynamic Programming

🪙 Dynamic Programming Medium

Longest Palindromic Substring

Longest Palindromic Substring explained: the 2D DP view and the simpler expand-around-center method in O(n²) time and O(1) space, tested Python, pitfalls.

Also searched as: longest palindromic substring expand around center · longest palindrome in a string · palindromic substring dp

🧮

Try it live Free

2D DP Table: LCS & Edit Distance

The DP Table lab shows a 2D table of string-prefix subproblems filling cell by cell; for palindromes the table is indexed by start and end, and each cell depends on the cell one step inward.

Also useful: Two Pointers

Open the playground →

The problem

Given a string, return its longest contiguous substring that reads the same forwards and backwards. If several have the same maximum length, any one is acceptable.

Input"babad"
Output"bab" (or "aba")
Input"cbbd"
Output"bb"

Even-length palindromes have a center between two characters.

The key insight

A palindrome is a palindrome with one matching character added on each side. In DP terms, s[i..j] is a palindrome if s[i] == s[j] and s[i+1..j-1] is one. Expanding outward from every possible center walks exactly those table cells without storing the table: there are 2n - 1 centers (each character and each gap).

Brute force first: Checking every one of the O(n²) substrings for being a palindrome costs O(n) each, O(n³) total.

Step-by-step approach

  1. For each index c, try two centers: (c, c) for odd lengths and (c, c + 1) for even lengths.
  2. From a center (lo, hi), move outward while both ends are in range and s[lo] == s[hi].
  3. When it stops, the palindrome is s[lo + 1 : hi].
  4. Keep the longest one seen and return it.

Python solution

PYTHON 3tested
def longest_palindrome(s):
    if not s:
        return ""
    best_lo, best_hi = 0, 1                 # s[best_lo:best_hi]

    def expand(lo, hi):
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        return lo + 1, hi                   # last valid window

    for c in range(len(s)):
        for lo, hi in (expand(c, c), expand(c, c + 1)):
            if hi - lo > best_hi - best_lo:
                best_lo, best_hi = lo, hi
    return s[best_lo:best_hi]

Complexity

TimeO(n²)
SpaceO(1)

There are 2n - 1 centers and each expansion can run up to O(n) steps. Only a few indices are stored. The 2D DP table version is also O(n²) time but O(n²) space.

Common mistakes

Frequently asked questions

What is the time and space complexity of Longest Palindromic Substring?

Expand around center is O(n²) time and O(1) space. The DP table approach is O(n²) time and O(n²) space. Manacher's algorithm achieves O(n) time.

Why are there 2n - 1 centers?

Odd-length palindromes are centered on one of the n characters; even-length ones are centered on one of the n - 1 gaps between adjacent characters.

Can I reverse the string and take the LCS?

Not directly. The longest common substring of s and reversed s can be a non-palindrome, such as in "abacdfgdcaba". You must also check that the matched positions line up.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Dynamic Programming Coin Change (DP) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.