Longest Palindromic Substring using Dynamic Programming

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

Solution❯

Understanding the Problem

We are given a string, and we need to find the longest substring within it that is a palindrome. A palindrome is a sequence of characters that reads the same forward and backward, like "racecar" or "madam".

Our task is to locate the longest such sequence that appears continuously in the string.

This problem is ideal for dynamic programming, because we can build the answer for longer substrings using the answers for shorter ones.

Step-by-Step Solution with Example

Step 1: Define what we want to track

We will use a 2D table dp[i][j], where each cell tells us whether the substring from index i to j (inclusive) is a palindrome.

Step 2: Initialize all substrings of length 1

Every single character is a palindrome by itself. So we set dp[i][i] = true for all i.

Step 3: Handle substrings of length 2

These need special treatment because the general rule (checking the inside substring) doesn’t apply here. We simply check if s[i] == s[i+1]. If true, we set dp[i][i+1] = true.

Step 4: Fill the table for substrings of length ≥ 3

We use a nested loop to check all substrings from length 3 up to the full string. For each substring s[i..j], we check:

If s[i] == s[j], and
If dp[i+1][j-1] is true (the substring inside is already a palindrome)

If both are true, then s[i..j] is a palindrome and we set dp[i][j] = true.

Step 5: Keep track of the longest palindrome found

While filling the table, whenever we find a true in dp[i][j], we check if the length of this palindrome is longer than what we’ve seen so far. If it is, we update the starting index and length of the longest palindrome.

Step 6: Extract the result

After filling the table, we use the recorded start index and length to extract the longest palindromic substring from the original string and return it.

Example: Input = "babad"

Let’s apply our logic to the input "babad".

Length 1 substrings: All set to true.
Length 2 substrings: "ba", "ab", "ad" → none are palindromes.
Length 3 substrings: "bab" and "aba" are palindromes.

So the longest palindromic substrings are "bab" and "aba". We return either.

Edge Cases

Empty string: Return an empty string directly.
All characters are the same: Example: "aaaa" → return the whole string as it is already a palindrome.
No repeated characters: Example: "abc" → return any single character, since every single character is a palindrome.
Multiple valid results: As in "babad", both "bab" and "aba" are valid. We can return either one.

Finally

This dynamic programming approach ensures we don’t repeat calculations. It gives us an efficient O(n²) solution, suitable for strings up to around 1000 characters.

By starting from the smallest substrings and building up, we make sure that when we check if s[i..j] is a palindrome, we already know whether the smaller parts are palindromes.

This method is beginner-friendly once you understand how dynamic programming builds upon smaller solutions.

Algorithm Steps❯

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

Code

C++

Python

Java

Rust

Kotlin

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

char* longestPalindrome(char* s) {
    int n = strlen(s);
    static char res[1000];
    bool dp[n][n];
    memset(dp, false, sizeof(dp));

    int start = 0, maxLen = 1;
    for (int i = 0; i < n; i++) dp[i][i] = true;

    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i+1]) {
            dp[i][i+1] = true;
            start = i;
            maxLen = 2;
        }
    }

    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i+1][j-1]) {
                dp[i][j] = true;
                if (len > maxLen) {
                    start = i;
                    maxLen = len;
                }
            }
        }
    }
    strncpy(res, s + start, maxLen);
    res[maxLen] = '\0';
    return res;
}

int main() {
    char input[] = "babad";
    printf("Longest Palindromic Substring: %s\n", longestPalindrome(input));
    return 0;
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n^2)	We fill an n x n DP table and check each substring for palindromicity.
Average Case	O(n^2)	All substrings are checked; DP avoids redundant recalculations.
Worst Case	O(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.

⬅ Previous TopicSort Characters by Frequency - Optimal HashMap and Heap Approach

Next Topic ⮕Find Longest Palindromic Substring Without Dynamic Programming

Comments

Loading comments...