Dynamic Programming (DP) approach for the Longest Palindromic Substring problem and solution in Java and Python

Let’s go through the Dynamic Programming (DP) approach for the Longest Palindromic Substring problem — with a clear explanation, example table, and Java/Python code.

---

🧩 Problem Recap

Find the longest palindromic substring in a given string s.

Example:

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

---

💡 Dynamic Programming Approach

🧠 Key Idea

We define:

dp[i][j] = true  if the substring s[i...j] is a palindrome

So:

• A single character is always a palindrome → dp[i][i] = true

• For two characters, it’s a palindrome if s[i] == s[j]

• For more than two characters, it’s a palindrome if:

  s[i] == s[j] && dp[i+1][j-1] == true
  

---

🪜 Steps

1. Create a 2D DP table (n x n) initialized to false

2. Mark all single letters as true

3. Expand substring length from 2 → n:

   • If the current substring s[i...j] is a palindrome → mark it
   • Keep track of the longest one

---

🧮 Example:

s = "babad"

i\j	0 (b)	1 (a)	2 (b)	3 (a)	4 (d)
0 (b)	T	F	T	F	F
1 (a)		T	F	T	F
2 (b)			T	F	F
3 (a)				T	F
4 (d)					T

Here "bab" and "aba" are both valid palindromic substrings.

---

✅ Java Solution (DP)

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

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

        // Every single character is palindrome
        for (int i = 0; i < n; i++)
            dp[i][i] = true;

        // Fill DP table
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;

                if (s.charAt(i) == s.charAt(j)) {
                    if (len == 2 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        if (len > maxLen) {
                            start = i;
                            maxLen = len;
                        }
                    }
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
}

---

✅ Python Solution (DP)

def longestPalindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s

    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1

    # Each character is palindrome
    for i in range(n):
        dp[i][i] = True

    # Build table
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2 or dp[i + 1][j - 1]:
                    dp[i][j] = True
                    if length > max_len:
                        start = i
                        max_len = length

    return s[start:start + max_len]

---

⚖️ Complexity

Operation	Time	Space
Dynamic Programming	O(n²)	O(n²)

---

🎯 When to Use Which

Method	Best When	Complexity
Expand Around Center	Simpler, O(1) space	O(n²)
Dynamic Programming	Teaching/trace visualization	O(n²) time, O(n²) space
Manacher’s Algorithm	Advanced, very fast	O(n) time

---

🧠 Analogy

Imagine marking matching mirrors in a word: Whenever the letters at both ends match, you “light up” that substring in your table. The longest lit-up area = your longest palindrome ✨

---