Skip to main content
DSA patterns

Longest Palindromic Substring

mediumStringsAmazonMicrosoftTCS Digital

Problem statement

You are given a string s. A palindrome is a string that reads the same forwards and backwards, like "level" or "aba". Find the longest substring of s (a contiguous run of its characters) that is a palindrome, and return it.

If more than one substring is a palindrome of the same maximum length, returning any one of them is accepted.

Examples

Example 1

Input: s = "babad"

Output: "bab"

Explanation: "bab" reads the same forwards and backwards and is the longest such substring. "aba" is also length 3 and equally valid.

Example 2

Input: s = "cbbd"

Output: "bb"

Explanation: "bb" is the longest run in "cbbd" that reads the same forwards and backwards; no longer substring does.

Hints

Hint 1: A single character is always a palindrome, so the answer is never empty — the real question is how far a palindrome can be stretched from some starting point.

Approach

Optimal: Expand around center

Intuition

Every palindrome has a center: either a single middle character (odd length, like "level", centered on the 'v') or a gap between two equal characters (even length, like "noon", centered between the two 'o's). There are exactly 2n-1 such centers in a string of length n. Instead of building a table, we can try each center directly: start with the smallest palindrome at that center (one character, or an empty gap) and expand outward one step at a time in both directions as long as the characters on each side keep matching. The moment they stop matching, we know exactly how far the palindrome around that center reaches, and we compare its length with the best found so far.

This needs no extra array — we only track a handful of numbers as we expand — so the space drops from the DP table's O(n²) to O(1), while the time stays O(n²). This is the version most engineers reach for in an interview: same time complexity as the DP approach, but far less memory and no table to set up.

Steps

  1. Set best to an empty range.
  2. For each index i from 0 to n-1:
    • Expand around the single-character center at i (odd length) and update best if this palindrome is longer.
    • Expand around the gap between i and i+1 (even length) and update best if this palindrome is longer.
  3. "Expand around a center" means: set two pointers left and right at the center, then while left >= 0 and right < n and s[left] == s[right], move left one step left and right one step right. When the loop stops, the palindrome is s[left+1 .. right-1].
  4. Return best.

Dry run

s = "babad"

i odd center expands to even center expands to best after
0 "b" (len 1) "" (s[0]≠s[1]) "b"
1 "bab" (s[0]==s[2]) "" (s[1]≠s[2]) "bab"
2 "aba" (len 3, not longer) "" "bab"
3 "a" "" "bab"
4 "d" out of bounds "bab"

Edge cases: an empty gap naturally produces a length-0 "palindrome" that never beats a real character, so single-character strings still return correctly; an all-same-character string (like "aaaa") expands all the way to the full string.

Complexity

Time O(n²) - there are 2n-1 possible centers (n single-character centers and n-1 gaps between characters), and expanding around a center can take up to O(n) steps in the worst case (e.g. a string of all identical characters), so the total work is O(n) centers × O(n) expansion = O(n²). This matches the DP approach's time.

Space O(1) - extra — we only track a few index variables while expanding, never a full table.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        def expand(left: int, right: int):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return left + 1, right - 1

        best_start, best_end = 0, 0
        for i in range(len(s)):
            odd_start, odd_end = expand(i, i)
            if odd_end - odd_start > best_end - best_start:
                best_start, best_end = odd_start, odd_end

            even_start, even_end = expand(i, i + 1)
            if even_end - even_start > best_end - best_start:
                best_start, best_end = even_start, even_end

        return s[best_start:best_end + 1]


if __name__ == "__main__":
    print(Solution().longestPalindrome("babad"))  # bab (or aba)
    print(Solution().longestPalindrome("cbbd"))  # bb
RecapThe whole problem in a few lines, for the night before
  • Spot it: the longest substring that reads the same both ways
  • Idea: expand around each centre; try both odd (one centre) and even (two centres) palindromes and keep the longest
  • Cost: O(n²) time, O(1) space
  • Trap: forgetting the even-length centres misses answers like "abba"

Interview follow-ups

  • What if you needed to count all palindromic substrings, not just find the longest one?

    The same expand-around-center technique works: for each of the 2n-1 centers, every successful expansion step corresponds to one more palindromic substring. Instead of tracking only the longest one, add 1 to a running count each time the characters match during expansion. This keeps the same O(n²) time and O(1) extra space.

  • The input can be up to 10^7 characters instead of 1000 — how would you approach it?

    At that size, O(n²) is far too slow (on the order of 10^14 operations), so we'd need Manacher's algorithm, which finds the longest palindromic substring in O(n) time by reusing the results of earlier expansions instead of restarting from scratch at each center. It's more intricate to implement correctly, but it's the standard solution once the input size rules out any quadratic approach.

Frequently asked questions

Both run in O(n²) time, but expanding around centers only needs a few integer variables, while the DP table needs O(n²) memory. For a large input the memory difference matters a lot, and the expand-around-center code is also shorter to write under time pressure, so most engineers lead with it once they've mentioned that the DP idea exists as an alternative.

Yes — Manacher's algorithm solves this in O(n) time by cleverly reusing information from centers already expanded. The underlying idea and its edge-case handling are intricate enough that they go beyond what a typical DevOps/SRE/Platform coding round expects. Knowing that a linear-time algorithm exists, and being able to name it, is usually enough.

The problem accepts any one of them. Both solutions above naturally return the first longest one found, because they only update best when a strictly longer palindrome is found, never when one of equal length appears.

Reversing the whole string and checking if it equals the original only tells you whether the entire string is a palindrome. You need to check every possible substring, since the longest palindrome is very often shorter than the whole string — "babad" itself is not a palindrome, but it contains one.

It's a general string-processing and algorithmic-reasoning question that regularly appears in general software-engineering rounds at infra-focused companies. It tests whether you can reason precisely about indices, edge cases and time/space trade-offs — the same care that matters when parsing logs, config strings and other structured text.