Problem Description

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

A palindrome is a string that reads the same forwards and backwards. For example, "racecar" is a palindrome, as is "noon". A substring is a contiguous sequence of characters within the string.

The problem asks you to identify the longest substring of s that forms a palindrome. If there are multiple palindromic substrings with the same maximum length, you can return any one of them.

For example:

• If s = "babad", the answer could be either "bab" or "aba" since both are palindromic substrings of length 3
• If s = "cbbd", the answer would be "bb"
• If s = "a", the answer would be "a" itself

The solution uses dynamic programming with a 2D table f[i][j] where each entry indicates whether the substring from index i to index j is a palindrome. The algorithm works by:

1. Initializing all single characters as palindromes (f[i][i] = True)
2. Checking longer substrings by comparing characters at positions i and j
3. If s[i] == s[j], then the substring s[i..j] is a palindrome if and only if s[i+1..j-1] is also a palindrome
4. Tracking the starting position (k) and length (mx) of the longest palindrome found
5. Returning the substring from position k with length mx

The time complexity is O(n²) where n is the length of the string, as we need to check all possible substrings. The space complexity is also O(n²) for the DP table.

Intuition

The key insight for solving this problem is recognizing that palindromes have a recursive structure. A string is a palindrome if its first and last characters match AND the substring between them is also a palindrome.

Think about checking if "racecar" is a palindrome. We see that r equals r at both ends. But that's not enough - we also need "aceca" to be a palindrome. Similarly, "aceca" is a palindrome if a equals a and "cec" is a palindrome, and so on.

This recursive relationship suggests we can build up our answer from smaller substrings to larger ones. If we already know whether all smaller substrings are palindromes, we can quickly determine if a larger substring is a palindrome by just checking its outer characters.

This leads us to dynamic programming. We can create a table where f[i][j] tells us whether the substring from index i to j is a palindrome. The beauty is that we can fill this table systematically:

1. Every single character is a palindrome by itself (base case)
2. For any substring s[i..j], if s[i] != s[j], it's definitely not a palindrome
3. If s[i] == s[j], then we just need to check if s[i+1..j-1] is a palindrome

The tricky part is the order of computation. Since f[i][j] depends on f[i+1][j-1], we need to compute smaller substrings before larger ones. This is why the code iterates i backwards (from n-2 to 0) and j forwards (from i+1 to n-1) - this ensures that when we compute f[i][j], the value f[i+1][j-1] has already been computed.

As we build the table, we keep track of the longest palindrome found so far by updating the starting position and length whenever we find a longer one.

Learn more about Two Pointers and Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming with a 2D boolean table to track palindromic substrings.

Data Structure Setup:

• Create a 2D table f[i][j] where f[i][j] = True means substring s[i..j] is a palindrome
• Initialize all entries to True initially (this handles the base case where i == j, single characters)
• Track the longest palindrome with variables k (starting index) and mx (length), initialized as k = 0, mx = 1

Core Algorithm: The implementation follows a specific iteration pattern to ensure dependencies are resolved correctly:

1. Outer loop: Iterate i from n-2 down to 0 (backwards)

   • We start from n-2 because when i = n-1, there are no valid j > i positions to check

2. Inner loop: For each i, iterate j from i+1 to n-1 (forwards)

   • This ensures we're only checking substrings of length 2 or more

3. Palindrome Check Logic:

   f[i][j] = False  # Initialize as not palindrome
   if s[i] == s[j]:
       f[i][j] = f[i+1][j-1]

   • First assume substring is not a palindrome
   • If outer characters match (s[i] == s[j]), check the inner substring
   • The value f[i+1][j-1] tells us if the inner substring is a palindrome
   • Due to our iteration order, f[i+1][j-1] is already computed when we need it

4. Track Maximum:

   • Whenever we find a palindrome (f[i][j] = True)
   • Check if its length j - i + 1 exceeds current maximum mx
   • If yes, update k = i and mx = j - i + 1

Why This Iteration Order Works:

• When computing f[i][j], we need f[i+1][j-1]
• Since i+1 > i and j-1 < j, we need to compute rows from bottom to top (i decreasing)
• Within each row, we compute columns from left to right (j increasing)
• This guarantees all dependencies are satisfied

Return Result: Finally, return the substring s[k : k + mx] which represents the longest palindrome found, starting at index k with length mx.

The time complexity is O(n²) as we check all possible substring pairs, and space complexity is O(n²) for the DP table.

Example Walkthrough

Let's walk through the algorithm with s = "babad".

Initial Setup:

• String: s = "babad" (indices 0-4)
• Create a 5×5 table f[i][j] initialized to True
• Variables: k = 0, mx = 1 (initially the first character "b")

Iteration Process:

When i = 3 (starting from n-2 = 3):

• j = 4: Check substring "a[3]d[4]"
  • s[3] ≠ s[4] ('a' ≠ 'd')
  • f[3][4] = False

When i = 2:

• j = 3: Check substring "b[2]a[3]"
  • s[2] ≠ s[3] ('b' ≠ 'a')
  • f[2][3] = False
• j = 4: Check substring "b[2]ad[4]"
  • s[2] ≠ s[4] ('b' ≠ 'd')
  • f[2][4] = False

When i = 1:

• j = 2: Check substring "a[1]b[2]"
  • s[1] ≠ s[2] ('a' ≠ 'b')
  • f[1][2] = False
• j = 3: Check substring "a[1]ba[3]"
  • s[1] = s[3] ('a' = 'a')
  • f[1][3] = f[2][2] = True (single character 'b' is palindrome)
  • Found palindrome "aba" of length 3 > mx(1)
  • Update: k = 1, mx = 3
• j = 4: Check substring "a[1]bad[4]"
  • s[1] ≠ s[4] ('a' ≠ 'd')
  • f[1][4] = False

When i = 0:

• j = 1: Check substring "b[0]a[1]"
  • s[0] ≠ s[1] ('b' ≠ 'a')
  • f[0][1] = False
• j = 2: Check substring "b[0]ab[2]"
  • s[0] = s[2] ('b' = 'b')
  • f[0][2] = f[1][1] = True (single character 'a' is palindrome)
  • Found palindrome "bab" of length 3 = mx(3)
  • No update needed (same length)
• j = 3: Check substring "b[0]aba[3]"
  • s[0] ≠ s[3] ('b' ≠ 'a')
  • f[0][3] = False
• j = 4: Check substring "b[0]abad[4]"
  • s[0] ≠ s[4] ('b' ≠ 'd')
  • f[0][4] = False

Final DP Table (True/False):

    0  1  2  3  4
0 [ T  F  T  F  F ]
1 [ T  T  F  T  F ]
2 [ T  T  T  F  F ]
3 [ T  T  T  T  F ]
4 [ T  T  T  T  T ]

Result:

• Return s[k : k + mx] = s[1:4] = "aba"
• The algorithm found "aba" as the longest palindrome (length 3)

Note: The algorithm could also have returned "bab" if we had updated k when finding palindromes of equal length. Both are valid answers.

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2), where n is the length of the string s. This is because the code uses two nested loops - the outer loop iterates from n-2 to 0 (approximately n iterations), and the inner loop iterates from i+1 to n-1 for each i. The total number of iterations across both loops is approximately n*(n-1)/2, which simplifies to O(n^2).

The space complexity is O(n^2), where n is the length of the string s. This is due to the 2D boolean array f of size n x n that stores whether each substring s[i:j+1] is a palindrome. The array requires n^2 space to store all possible substring palindrome states. The additional variables k and mx only require O(1) space, so the overall space complexity remains O(n^2).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Initialization of the DP Table

The Pitfall: Many implementations mistakenly initialize the entire DP table as False, forgetting that single characters are always palindromes. This leads to incorrect results when checking substrings of length 2.

Why It Happens: When checking if s[i..j] is a palindrome where j = i + 1 (substring of length 2), the code checks dp[i+1][j-1] which becomes dp[i+1][i]. If this wasn't properly initialized as True, the algorithm incorrectly concludes that two matching characters don't form a palindrome.

Example of Incorrect Code:

# WRONG: This initialization causes issues
dp = [[False] * n for _ in range(n)]  # All False including diagonals

The Solution: Initialize the diagonal elements (where i == j) as True since single characters are palindromes:

# CORRECT: Initialize with True to handle base cases
dp = [[True] * n for _ in range(n)]

Or explicitly set diagonal values:

dp = [[False] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = True  # Single characters are palindromes

2. Wrong Iteration Order Leading to Uncomputed Dependencies

The Pitfall: Iterating in the wrong order causes the algorithm to access dp[i+1][j-1] before it's been computed, leading to incorrect results.

Example of Incorrect Iteration:

# WRONG: Top-down iteration doesn't guarantee dependencies are ready
for i in range(n):  # Going forward instead of backward
    for j in range(i + 1, n):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j-1]  # dp[i+1][j-1] might not be computed yet!

The Solution: Always iterate i from n-2 down to 0 (backwards) to ensure dp[i+1][j-1] is computed before dp[i][j]:

# CORRECT: Bottom-up approach ensures dependencies are satisfied
for i in range(n - 2, -1, -1):  # Backward iteration
    for j in range(i + 1, n):    # Forward iteration
        # Now dp[i+1][j-1] is guaranteed to be computed

3. Not Handling Edge Cases for Short Substrings

The Pitfall: When j = i + 1 (checking a 2-character substring), accessing dp[i+1][j-1] becomes dp[i+1][i], which crosses the diagonal. Without proper initialization, this can cause index errors or incorrect results.

The Solution: The initialization of dp as all True elegantly handles this case. When checking a 2-character substring where both characters match, dp[i+1][i] correctly returns True, confirming the palindrome.

Alternatively, you can add explicit length checks:

if s[i] == s[j]:
    if j - i == 1:  # Two characters
        dp[i][j] = True
    else:  # More than two characters
        dp[i][j] = dp[i+1][j-1]