Longest Palindromic Substring using Dynamic Programming

Contents

ProblemExamplesVisualizationSolutionAlgorithmCodeTimeSpace

Problem Statement❯

Given a string s, your task is to find the longest palindromic substring within it.

  • A palindrome is a sequence of characters that reads the same forward and backward.
  • Your goal is to return the longest continuous segment of the input string that forms a palindrome.

If multiple substrings of the same maximum length exist, you can return any one of them.

If the input string is empty, return an empty string.

Examples❯

Input String Output Description
"babad" "bab" or "aba" Both "bab" and "aba" are valid palindromes of length 3
"cbbd" "bb" The longest palindrome is "bb" of length 2
"a" "a" Single character is always a palindrome
"ac" "a" or "c" No longer palindrome exists, return any single character
"racecar" "racecar" The entire string is a palindrome
"aacabdkacaa" "aca" "aca" is the longest palindromic substring
"" "" Empty input string returns empty output

Visualization Player

Solution❯

To find the longest palindromic substring in a given string, we look for sequences that read the same forward and backward. This problem is a perfect candidate for dynamic programming because we can build answers to bigger problems (long substrings) using answers to smaller problems (short substrings).

What’s the core idea?

A substring is a palindrome if the characters at the ends are equal and the part in between is also a palindrome. So we use a table (2D array) to record whether each substring s[i..j] is a palindrome.

How does dynamic programming help?

We create a 2D boolean table dp[i][j] where each cell tells us if the substring from index i to j is a palindrome. Once we know the result of smaller substrings, we can reuse that information to determine if a larger substring is also a palindrome.

How do we fill the table?

  • Substrings of length 1: Every single character is a palindrome. So we set dp[i][i] = true.
  • Substrings of length 2: These need special handling. We can't apply the general DP rule (checking the inner substring) because there's nothing between two characters. So instead, we just check if s[i] == s[i+1], and if so, mark dp[i][i+1] = true.

Why do this separately? If we applied the usual rule dp[i+1][j-1] here, we’d be accessing invalid indices when i+1 > j-1. So we handle 2-letter substrings directly and use them as a base to build longer palindromes like "abba".

  • Substrings of length ≥ 3: For any substring s[i..j], we check:
    • if s[i] == s[j]
    • and if dp[i+1][j-1] is true (i.e., the inner part is already a palindrome)
    If both conditions are met, we mark dp[i][j] = true.

How do we track the result?

While filling the dp table, we keep track of the longest palindrome found so far. If we find a new valid palindrome that’s longer than the previous one, we update the starting index and max length. At the end, we extract and return the longest substring using these values.

What about special cases?

  • Empty input: If the input string is empty, we return an empty string.
  • Multiple answers: For strings like "babad", both "bab" and "aba" are valid. We can return either.

Why this works efficiently

Without DP, we might check the same substring repeatedly. With DP, once we compute whether s[i..j] is a palindrome, we store it and never recompute it again. This gives us an efficient O(n²) solution, which works well for strings up to 1000 characters.

Algorithm Steps❯

  1. Let n be the length of the input string s.
  2. Create a 2D boolean array dp[n][n].
  3. Every single character is a palindrome, so set dp[i][i] = true for all i.
  4. Check all substrings of length 2 and mark dp[i][i+1] = true if s[i] == s[i+1].
  5. For substrings longer than 2, set dp[i][j] = true if s[i] == s[j] and dp[i+1][j-1] == true.
  6. Track the start index and max length of the longest palindrome found.
  7. Return the substring using start index and max length.

Code

Java
Python
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
public class LongestPalindromicSubstringDP {
  public static String longestPalindrome(String s) {
    int n = s.length();
    if (n <= 1) return s;

    boolean[][] dp = new boolean[n][n];
    int start = 0, maxLength = 1;

    // All substrings of length 1 are palindromes
    for (int i = 0; i < n; i++) dp[i][i] = true;

    // Check for substrings of length 2
    for (int i = 0; i < n - 1; i++) {
      if (s.charAt(i) == s.charAt(i + 1)) {
        dp[i][i + 1] = true;
        start = i;
        maxLength = 2;
      }
    }

    // Check substrings longer than 2
    for (int len = 3; len <= n; len++) {
      for (int i = 0; i <= n - len; i++) {
        int j = i + len - 1;
        if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
          dp[i][j] = true;
          if (len > maxLength) {
            start = i;
            maxLength = len;
          }
        }
      }
    }
    return s.substring(start, start + maxLength);
  }

  public static void main(String[] args) {
    String input = "babad";
    System.out.println("Longest Palindromic Substring: " + longestPalindrome(input));
  }
}

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n^2)We fill an n x n DP table and check each substring for palindromicity.
Average CaseO(n^2)All substrings are checked; DP avoids redundant recalculations.
Worst CaseO(n^2)The algorithm needs to check all possible substrings using nested loops.

Space Complexity

O(n^2)

Explanation: We use a 2D boolean table to store whether substrings are palindromes.