AlgoMaster Logo

Longest Palindromic Substring

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to find the longest contiguous substring that is a palindrome. A palindrome reads the same forwards and backwards, like "aba" or "abba". There can be multiple valid answers (as in Example 1), and returning any one of them is accepted.

Palindromes have a useful structure. Every palindrome is symmetric around a center, and it grows outward from that center one character at a time. A single character is a palindrome, and so is any pair of identical adjacent characters. The work is finding the longest such substring efficiently.

That symmetry leads to the better approaches. A string of length n has only 2n - 1 possible centers (each character, plus each gap between adjacent characters), so we can check every center instead of every substring.

Key Constraints:

  • 1 <= s.length <= 1000. With n at most 1000, an O(n^2) solution runs comfortably. An O(n^3) solution does roughly 10^9 operations at the limit, which is borderline.
  • s contains only digits and English letters, so there are no unicode or case-folding edge cases.
  • The string is never empty, so the answer always has length at least 1.

Approach 1: Brute Force

Intuition

Check every possible substring and test whether it is a palindrome. For each pair of indices (i, j) with i <= j, take the substring s[i..j], test whether it reads the same forward and backward, and keep the longest one that passes.

To test a substring, compare characters from the outside in: s[i] against s[j], then move inward. If every pair matches, it is a palindrome.

Algorithm

  1. Initialize variables to track the start index and length of the longest palindrome found (start with the first character as the default answer).
  2. For each starting index i from 0 to n-1:
    • For each ending index j from i to n-1:
      • Check if the substring s[i..j] is a palindrome.
      • If it is and its length exceeds the current best, update the best.
  3. Return the longest palindromic substring found.

Visualization and Code

Loading animation...

The bottleneck is redundant palindrome checking. For every substring we re-verify from scratch, ignoring the symmetry of palindromes. The next approach works from each center outward, so a longer palindrome reuses the comparisons already made for the shorter one inside it.

Approach 2: Expand Around Center

Intuition

Every palindrome is symmetric around its center, so instead of checking every substring we check every center and expand outward from it.

A string of length n has 2n - 1 centers, not n, because palindromes come in two forms. Odd-length palindromes are centered on a character (like "aba"), and even-length palindromes are centered between two characters (like "abba"). That gives n character centers and n-1 gap centers.

For each center, expand outward while the characters on both sides match, and stop at the first mismatch or string boundary. The longest expansion from any center is the answer.

Algorithm

  1. Initialize variables to track the start and end indices of the longest palindrome found.
  2. For each index i from 0 to n-1:
    • Expand around center i for odd-length palindromes (single character center).
    • Expand around center (i, i+1) for even-length palindromes (two character center).
    • For each expansion, move left pointer leftward and right pointer rightward while characters match.
    • Update the longest palindrome if the current expansion is longer.
  3. Return the substring corresponding to the longest palindrome found.

Visualization and Code

Loading animation...

This approach is O(n^2) time with O(1) space, which is the best space we can do here. The next approach reaches the same time bound through dynamic programming, building a table that records whether each substring is a palindrome.

Approach 3: Dynamic Programming

Intuition

A substring s[i..j] is a palindrome when two conditions hold: the outer characters match (s[i] == s[j]), and the inner substring s[i+1..j-1] is also a palindrome. That self-referential definition maps onto dynamic programming.

Build a 2D table where dp[i][j] is true when the substring from index i to j is a palindrome. Fill it from shorter substrings to longer ones. Every single character is a palindrome (the base case), and every pair of identical adjacent characters is a palindrome. For length 3 and up, apply the two conditions, reading the already-computed dp[i+1][j-1].

This is not faster than expand-around-center (both are O(n^2) time, and this uses more space), but the table answers "is s[i..j] a palindrome?" in O(1) and stays available afterward, which is useful when a larger problem needs many such queries.

Algorithm

  1. Create a 2D boolean table dp of size n x n, initialized to false.
  2. Mark all single characters as palindromes: dp[i][i] = true for all i.
  3. Check all pairs of adjacent characters: dp[i][i+1] = true if s[i] == s[i+1].
  4. For each substring length from 3 to n:
    • For each starting index i:
      • Compute ending index j = i + length - 1.
      • Set dp[i][j] = true if s[i] == s[j] and dp[i+1][j-1] is true.
  5. Track the longest palindrome found during table construction.
  6. Return the corresponding substring.

Visualization and Code

Loading animation...