Longest Palindromic Substring – LeetCode Problem 5 Explained With Java (Dynamic Programming Approach)

Are you preparing for coding interviews and struggling with LeetCode Problem 5: Longest Palindromic Substring? In this post, you’ll learn a step-by-step dynamic programming solution in Java to efficiently solve this classic problem. Complete with code, explanation, and tips — this guide will help you ace interview questions involving string manipulation.

📌 Problem Statement

Given a string s, find and return the longest palindromic substring within it.

A palindrome is a sequence that reads the same forward and backward — for example, "madam", "racecar", or "noon".

Example:

Input: s = "babad"
Output: "bab" or "aba"

🚀 Why Use Dynamic Programming?

A brute-force solution checks all substrings, leading to a time complexity of O(n³). However, using dynamic programming (DP) reduces this to O(n²) by storing previously computed results in a 2D table.

🧠 How the Dynamic Programming Approach Works

Step-by-Step Breakdown:

Create a DP Table: dp[i][j] is true if the substring s[i...j] is a palindrome.
Base Cases:
- Single characters are always palindromes (dp[i][i] = true).
- Two characters are palindromes if they’re equal.
Check Longer Substrings:
- For substrings longer than 2 characters, check if the first and last characters are equal and if the inner substring is a palindrome.
Track the Longest Palindrome:
- Keep updating the start index and length of the longest valid palindrome found.

💻 Java Code: Longest Palindromic Substring

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;

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

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

        // Check for palindromes 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 for 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);
    }
}

📊 Time and Space Complexity

Time Complexity: O(n²) – Two nested loops for all substring combinations.
Space Complexity: O(n²) – Due to the 2D DP table used for storing palindrome checks.

🔍 Example Walkthrough

Let’s take s = "babad":

"b" and "a" are palindromes (length 1).
"bab" is a palindrome because b == b and "a" in between is also a palindrome.
"aba" is also valid and can be another answer depending on the DP filling order.

🟢 Final result: "bab" or "aba".

⚙️ Real-Life Use Cases

🧬 Bioinformatics: Detect palindromic DNA/RNA sequences.
🛡 Security: Identify symmetric keys or patterns in encryption.
📚 Text Processing: Spot palindromic phrases in natural language datasets.

❗ Common Mistakes to Avoid

Skipping Base Cases: Not initializing single-character or two-character substrings.
Incorrect Index Ranges: Be careful with i, j, and len calculations.
Memory Overhead: For large strings, consider the Expand Around Center approach to save space.

🔁 Alternative Approaches

1. Expand Around Center

Time: O(n²)
Space: O(1)
Efficient for interviews when memory is a constraint.

2. Manacher’s Algorithm

Time: O(n)
Space: O(n)
Advanced and less intuitive, but optimal for competitive coding.

🤔 Why Interviewers Love This Problem

This is a favorite string problem at top tech companies like Google, Amazon, Microsoft, and Meta. It tests your understanding of:

Substring boundaries
Dynamic programming fundamentals
Optimization of brute-force logic

✅ Summary

The Longest Palindromic Substring problem is a must-practice for any developer preparing for technical interviews. The dynamic programming solution helps you build a strong foundation for solving complex string problems efficiently.

🔗 What’s Next?

Explore related problems to sharpen your skills:

🔸 Longest Palindromic Subsequence
🔸 Palindromic Substrings Count
🔸 Minimum Insertions to Make a String Palindrome

Keep practicing, keep improving — and you’ll be interview-ready in no time! 🚀💻

Longest Palindromic Substring – LeetCode Problem 5 Explained with Java (Dynamic Programming Approach)