[[Dynamic Programming Primer]]

Problem

You are given one string, s. Your goal is to find the longest substring (a contiguous block) that is a palindrome.

Example: s = "babads". The answer is "bab" (or "aba"). Length is 3.

Brain storming

lets start with the basics a substring of string s is defined as s[start:end] start and end being the index inside this string that represent this substring. Why do we care about this? its because for a palindrome this play a very important role.

A palindrome is defined as a string where its reverse is also a valid string. for eg racecar is a palindrome since its reverse racecar is also a valid string.

So whatever logic we come up with we need both the start index and the end index of the subsequence to determine palindrome. Just like the previous problem [[Longest Common Subsequence]] if we need 2 variables to define a subproblem then its a 2D dynamic programming problem

Imagining “Substrings” and the DP Grid

Okay, we’ve established it’s 2D. But the meaning of the grid is different now. It’s not about two different strings; it’s about one string.

Let s = "babad". Our dp grid will be 5 x 5.

The grid is a lookup table for the answer to the question:DP[i][j] “Is this substring a palindrome?”

      b   a   b   a   d   (end index, j)
    +---+---+---+---+---+
b 0 | . | . | . | . | . |
    +---+---+---+---+---+
a 1 |   | . | . | . | . |
    +---+---+---+---+---+
b 2 |   |   | . | . | . |
    +---+---+---+---+---+
a 3 |   |   |   | . | . |
    +---+---+---+---+---+
d 4 |   |   |   |   | . |
    +---+---+---+---+---+

^
|
(start index, i)

(Note: We only care about the upper half of the grid where i <= j) why ? since i is the start index and j is the end index a string for eg s[3][1] doesn’t make any sense as it will be empty

Let’s pick an arbitrary cell: dp[1][3].

1. What does it mean?

   • i=1 is the start index.
   • j=3 is the end index.
   • This cell corresponds to the substring s[1...3], which is "aba".
   • dp[1][3] will hold the boolean value True because "aba" is a palindrome.

2. How do we calculate it? (The Story of a Single Cell) To solve for dp[i][j], we need a rule. For any string to be a palindrome, two things must be true.

   • Prompt 2 (The Recurrence): Let’s figure out dp[1][3] ("aba").
     1. Condition 1 (The Outsides): What must be true about the first and last characters of the substring s[i...j]?
     2. Condition 2 (The Insides): If the outer characters match, what must be true about the string between them? For "aba", the inner string is "b". For "racecar", it’s "aceca". How do we know if this inner string is a palindrome? (Hint: We can look up the answer for the inner substring s[i+1...j-1] in our dp table. Which cell is that?) Combine these two to form the recurrence: dp[i][j] = (condition_1) AND (condition_2).

3. The “First Move” Test (Base Cases): Our recurrence works for strings of length 3 or more. But what about the simplest cases?

   • Prompt 3 (The Base Cases):
     • What about dp[i][i]? (A substring of length 1, like "b"). Is it a palindrome?
     • What about dp[i][i+1]? (A substring of length 2, like "ba" or "bb"). Under what one condition is it a palindrome?

4. The Visualisation (Table Fill Order): Look at your recurrence. To compute dp[i][j], you need dp[i+1][j-1].

   • i+1 is the row below you.
   • j-1 is the column to the left of you.
   • Prompt 4 (The Order): If you need the answer from a cell “below-left” of you, can you fill the table in the standard top-to-bottom, left-to-right order? What order must you fill it in?

This is not your typical tabulation approach now its your memoization form of DP since dp[i][j] depends upon dp[i+1] a future value. So what we need to do is calculate values and then write down the answers as we build them. Also we would not be able to build this in the standard flow of DP grid (left-> right) (top->bottom)

Lets try to define the algorithm

1. Get the string length lets call it n
2. initialise a dp grid of nxn with false value as default
3. lets first calculate for base cases values
   1. string of length 1 , by definition they are palindrome
   2. string of length 2, if the first and the last characters are same then they are palindrome
   3. Store both these strings values in your DP grid hence getting are base cases jotted down
4. now for string of length 3 , we know for a fact we cannot go the standard way then how should we do it
   1. One way to do it try to fill the table in reverse bottom to top , right to left but we might face challenges writing that code
   2. The other way is to solve for length something we are already doing for strings of length 1 and 2 , we will try to solve for length of 3 and greater (till n+1) we can compute the start index as (n - length +1)
      1. lets take “babads” as example
         1. n= 6 length = 3 b then the substring is aba with its start index as b at 0 and end index d is 4 then we will iterate for each string of this length inside the string as for i in range(n-length +1) . here we will check for start index 0 , 1, 2, 3 . with these start indexes we will calculate the end index j as i + length -1 so the j becomes 2, 3,4,5 hence the substrings to check become
            1. s[0:2] = bab
            2. s[1:3] = aba
            3. s[2:4] = bad
            4. s[3:5] = ads
      2. Now we will have our substring to check with the outer and inner logic
         1. the outer logic will be simple s[i] == s[j]
         2. the inner logic would be dp[i+1][j-1]
         3. hence the final logic is dp[i][j] = (s[i]==s[j] and dp[i+1][j-1]

Below is the python implementation

s = "babads"
n = len(s)
if n < 2:
    # return s # Handle empty or single-character strings

# 1. Initialization
dp = [[False for _ in range(n)] for _ in range(n)]
longest_start = 0
max_len = 1 # Default answer is a single character

# 2. Base Case 1: Substrings of length 1
for i in range(n):
    dp[i][i] = True

# 3. Base Case 2: Substrings of length 2
for i in range(n - 1):
    if s[i] == s[i+1]:
        dp[i][i+1] = True
        # If we find a length-2 palindrome, update our answer
        longest_start = i
        max_len = 2

# 4. Main Logic: Substrings of length 3 and greater
for length in range(3, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        
        # --- The Core Recurrence ---
        # First, check if the inner substring is a palindrome AND
        # if the outer characters match.
        is_inner_palindrome = dp[i+1][j-1]
        if is_inner_palindrome and s[i] == s[j]:
            # If both are true, then the whole substring is a palindrome
            dp[i][j] = True
            
            # --- The Tracking Logic ---
            # Now that we've confirmed s[i..j] is a palindrome,
            # check if it's the new longest one.
            if length > max_len:
                max_len = length
                longest_start = i

# 5. Return the result
print(s[longest_start : longest_start + max_len])