Longest Palindromic Substring
Mastering the DP recurrence pattern

📋 Problem Statement

Given a string s, return the longest palindromic substring in s.

Example 1

Input:  s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
  

Example 2

Input:  s = "cbbd"
Output: "bb"
  

Constraints

1 ≤ s.length ≤ 1000
s consists of only digits and English letters.

We're going to build the intuition from the ground up — not just memorize the solution. By the end, you'll know how to derive the recurrence for any "optimal substring" problem.

1. What makes a palindrome?

A string s is a palindrome if it reads the same forwards and backwards:

"racecar" — outer chars match, and the inside is also a palindrome.

This is the recurrence in disguise:

The core insight

s[i..j] is a palindrome iff:

s[i] === s[j] — the outer characters match, AND
s[i+1 .. j-1] is a palindrome — the inner substring is also a palindrome.

Base cases: every single character is a palindrome. Two identical adjacent characters are a palindrome.

2. The recurrence relation

Let dp[i][j] = true if s[i..j] is a palindrome dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i+1][j-1]) └─ base: length 1 or 2 ─┘ └─ recurse to inside ─┘

Break this down:

j - i < 2 covers lengths 1 (i==j) and 2 (j==i+1). No inner substring needed — just check s[i]==s[j].
For length ≥ 3, we depend on the answer for a shorter substring — the classic DP hallmark.

Why this pattern is reusable

Any problem where the answer for [i..j] depends on [i+1..j-1] follows this exact shape:

dp[i][j] = f( s[i], s[j], dp[i+1][j-1] )

This shows up in: Palindrome Partitioning, Longest Palindromic Subsequence, Minimum Insertions to Form Palindrome, and many "interval DP" problems.

The key to recognizing DP applicability: the answer for a larger interval is built from the answer for a smaller interval. You fill the DP table diagonally — by increasing substring length.

3. Interactive DP table walkthrough

Choose an example string and step through how the DP table fills:

0 Click "Step Forward" to begin

Speed: 0.8s

4. How to fill the DP table (the traversal order)

You cannot fill row-by-row left-to-right, because dp[i][j] depends on dp[i+1][j-1] (the cell below-left).

Strategy: Fill by substring length.

The diagonal traversal

T
	T
		T
			T
				T

Pass 1: length=1 (diagonal)

Pass 2: length=2 (one off diagonal)

Pass 3: length=3 (two off diagonal)

... and so on until length=n.

// Fill by length
for (let len = 1; len <= n; len++) {
  for (let i = 0; i + len - 1 < n; i++) {
    let j = i + len - 1;
    // When filling [i][j], dp[i+1][j-1] is already computed
    // because i+1..j-1 has length len-2 < len
  }
}
  

This "diagonal fill" pattern is universal for interval DP. Whenever dp[i][j] depends on a strictly shorter interval, iterating by length guarantees correct dependency order.

5. The complete solution

/**
 * Longest Palindromic Substring — DP O(n²) time, O(n²) space
 * Pattern: Interval DP with dp[i][j] = (s[i]==s[j]) && (len<3 || dp[i+1][j-1])
 */
function longestPalindrome(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(false));
  let start = 0, maxLen = 1;

  // Base: every single char is a palindrome
  for (let i = 0; i < n; i++) dp[i][i] = true;

  // Fill by increasing substring length
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;

      if (s[i] !== s[j]) {
        dp[i][j] = false;     // Mismatch → not a palindrome
      } else if (len <= 3) {
        dp[i][j] = true;      // Length 2 or 3 with matching ends
      } else {
        dp[i][j] = dp[i+1][j-1]; // Recurrence: check inner substring
      }

      if (dp[i][j] && len > maxLen) {
        start = i;
        maxLen = len;
      }
    }
  }

  return s.substring(start, start + maxLen);
}

Space optimization: Since dp[i][j] only depends on row i+1, you can reduce to O(n) space with two rows. But for learning, the full table is clearer.

6. Recognizing this pattern in other problems

Problem	Recurrence	Traversal
Longest Palindromic Substring	`dp[i][j] = s[i]==s[j] && dp[i+1][j-1]`	By length
Longest Palindromic Subsequence	`dp[i][j] = s[i]==s[j] ? 2+dp[i+1][j-1] : max(dp[i+1][j], dp[i][j-1])`	By length
Palindrome Partitioning II (min cuts)	Use palindrome DP table + min-cut DP	By length
Stone Game / Burst Balloons	`dp[i][j] = max(dp[i][k] + dp[k][j] + ...)`	By length

The common thread: interval DP — the answer for [i..j] splits into smaller intervals. Always fill by increasing length.

7. Submissions — click to expand

▶ Submission #1 — Hash-map DP (first attempt) 4 bugs 6 issues

Click to expand

Your submitted code:

class Solution:

    def hash_array_set(self, dp: dict[int, int], i: str, j: str, val: bool):
        """Allows lookup in a hash array like an array in python"""
        try:
            assert dp[i]
        except KeyError:
            dp[i] = {}

        try:
            assert dp[i][j]
        except KeyError:
            dp[i][j] = False

        dp[i][j] = val

    def hash_array_get(self, dp: dict[int, int], i: str, j: str, val: bool):
        try:
            return dp[i][j]
        except KeyError:
            return False

    def longestPalindrome(self, s: str) -> str:

        if len(s) < 1:
            return '0'

        dp = {}
        longest_palindrome = ''

        # Length 2
        for idx in range(len(s) - 1):
            i, j = idx, idx+1
            if s[i] == s[j]:
                longest_palindrome = s[i:j+1]
            self.hash_array_set(dp, i, j, s[i] == s[j])

        # Length 3
        for idx in range(len(s) - 2):
            i, j = idx, idx + 2
            if s[i] == s[j]:
                longest_palindrome = s[i:j+1]
            self.hash_array_set(dp, i, j, s[i] == s[j])

        # Length 4+
        for str_len in range(4, len(s)):          ← BUG #1: off-by-one
            for idx in range(len(s) - str_len):
                i, j = idx, idx + str_len            ← BUG #4: j should be idx + str_len - 1
                if s[i] == s[j] and hash_array_get(dp, i+1, j-1):  ← BUG #3: missing self.
                    longest_palindrom = s[i:j+1]   ← BUG #2: typo (missing 'e')
                    break

        return longest_palindrome
      

Interviewer verdict: Would not pass 4 bugs (1 logical, 3 mechanical) + design concerns

🔴 Blocking Bugs

Bug #1 — Off-by-one in the outer loop BLOCKING

range(4, len(s)) stops at len(s)-1, so you never check the full string. For "babad" (len=5), you only check str_len=4. The substring "babad" itself is never evaluated. If the longest palindrome is the whole string, your code returns the wrong answer.

Fix:

range(4, len(s) + 1)

Bug #2 — Variable name typo: `longest_palindrom` BLOCKING

Inside the length≥4 loop, you write to longest_palindrom (missing an 'e'). This creates a new local variable — it never updates longest_palindrome. The function always returns whatever was found in the length-2 or length-3 passes. For any string where the longest palindrome has length ≥ 4, the result is wrong.

⚠️ This is the kind of bug that's very hard to spot in an interview because your brain autocorrects the spelling.

Bug #3 — Missing `self.` on `hash_array_get` BLOCKING

Inside the length≥4 loop you call hash_array_get(dp, i+1, j-1) without self.. This will throw a NameError at runtime — the function is never defined in local or global scope.

Bug #4 — Wrong `j` calculation: `j = idx + str_len` BLOCKING

This is the only logic-level bug — and it's subtle. Look at lengths 2 and 3:

Length 2 loop: you use j = idx + 1 — and s[i:j+1] slices 2 chars. ✓
Length 3 loop: you use j = idx + 2 — and s[i:j+1] slices 3 chars. ✓

But in the generalized loop, j = idx + str_len gives a substring of length str_len + 1, not str_len. For str_len=4, you're checking substrings of length 5. The range(len(s) - str_len) compensates by shrinking the loop range, but the two errors partially mask each other — until they don't.

Counterexample: "abba" — the whole string is a palindrome. But:

n=4, str_len=4:  range(4-4) = range(0) → empty loop
The full string is never checked. Result: "bb" ← WRONG
        

Fix:

j = idx + str_len - 1 (so the substring s[i:j+1] has exactly str_len characters)

🟡 Design / Code Quality Issues

Issue #4 — Edge case returns wrong sentinel

if len(s) < 1: return '0' — the character '0' is a valid English letter/digit and could appear in the input. An empty string should return "". Returning '0' is misleading and would fail test cases where the input is empty (though constraints say len≥1, it's sloppy).

Issue #5 — No base case for length 1

You never initialize dp[i][i] = True. The code works around this by special-casing lengths 2 and 3, but this is fragile. If you later refactored to unify the loops, the recurrence dp[i+1][j-1] would fail for substrings where the inner portion is length 1 (because hash_array_get returns False for unset keys).

Missing base cases = missing the foundation of DP. The interviewer wants to see you explicitly set up the base.

Issue #6 — Unnecessary special-casing of lengths 2 and 3

You have three separate loops (len=2, len=3, len≥4) when the general recurrence handles all of them. Length 2 (j-i+1=2): the inner substring dp[i+1][j-1] doesn't exist (i+1 > j-1), so the recurrence needs a guard. Length 3: the inner substring is length 1, which is always a palindrome, so s[i]==s[j] suffices. But all this collapses into one loop with the len <= 3 guard — exactly what the canonical solution does.

The unified approach:

if s[i] == s[j] and (len <= 3 or dp[i+1][j-1])

Issue #7 — Anti-pattern: `try/except assert` for dict defaults

hash_array_set uses assert dp[i] inside a try/except to detect missing keys. This is non-idiomatic and confusing:

assert can be disabled with python -O, silently breaking the code
The idiomatic way is dp.setdefault(i, {}) or if i not in dp: dp[i] = {}
hash_array_get has an unused parameter val — dead code

Issue #8 — Type hints are wrong

dict[int, int] suggests values are int, but you're storing nested dicts of bools. The correct hint is dict[int, dict[int, bool]]. Wrong type hints signal to the interviewer that you're not thinking about the data structure's shape.

Issue #9 — Sparse hash-map buys nothing here

The idea of using a hash-map to "avoid storing all the data" is premature optimization. For n≤1000, an n×n list-of-lists uses ~8MB for booleans — negligible. The hash-map approach adds overhead (hashing, collisions), makes traversal harder, and doesn't reduce asymptotic complexity. The real space optimization is the two-row rolling array that drops O(n²)→O(n).

🟢 Fixed & Improved Solution

What changed and why:

Single unified loop — one for len in range(2, n+1) replaces three ad-hoc loops
Explicit base case — dp[i][i] = True is initialized up front
Proper 2D list — [[False]*n for _ in range(n)] is simpler, faster, and idiomatic
Variable name consistency — no typos, single source of truth for the longest palindrome
Correct edge case — returns "" for empty input, s[0] for single-char input

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ""

        # dp[i][j] = True  ⇔  s[i..j] is a palindrome
        dp = [[False] * n for _ in range(n)]

        start = 0
        max_len = 1

        # Base case: every single character is a palindrome
        for i in range(n):
            dp[i][i] = True

        # Fill by increasing substring length
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1

                if s[i] != s[j]:
                    dp[i][j] = False
                elif length <= 3:
                    # length 2: two identical chars → palindrome
                    # length 3: s[i]==s[j] → palindrome (middle doesn't matter)
                    dp[i][j] = True
                else:
                    # Recurrence: outer match + inner palindrome
                    dp[i][j] = dp[i + 1][j - 1]

                if dp[i][j] and length > max_len:
                    start = i
                    max_len = length

        return s[start:start + max_len]
      

🎯 Key Takeaway

You understood the recurrence perfectly — this is the hard part. The intuition that dp[i][j] = s[i]==s[j] and dp[i+1][j-1] and that you fill by increasing length is exactly right. The hash-map idea shows you're thinking about space. The separate handling of base lengths shows correct DP thinking.

However, three of the four bugs come from translating the recurrence into loop indices. Bug #4 is especially instructive — you correctly derived j = idx+1 for length 2 and j = idx+2 for length 3 (both are idx + (length - 1)), but wrote j = idx + str_len in the generalized loop (should be idx + str_len - 1). This is a classic off-by-one that happens when you generalize from concrete cases without verifying the formula.

Derive indices from first principles: write j = i + length - 1 explicitly — don't guess from the small-case pattern
Test your code mentally on short inputs like "abba" — it exposes index errors the fastest
Unify, don't multiply: three loops hint that one loop could replace them, which would have forced you to get the index formula right
Check your variable names — a typo that creates a new variable is a silent killer in Python (no compiler to catch it)

▶ Submission #2 — Unified loop (second attempt) 3 bugs 5 issues

Click to expand

Progress from #1: Improved Fixed 3 of 4 bugs + 2 issues, but introduced new logical errors

What you fixed: ✅ unified three loops into one, ✅ added length-1 base case, ✅ fixed typo, ✅ fixed return sentinel, ✅ fixed type hints. What went wrong: the j calculation still has the off-by-one, the recurrence references dp[i][j] instead of dp[i+1][j-1], and the str_len <= 3 guard now fires for the wrong lengths.

Your submitted code:

class Solution:

    def hash_array_set(self, dp: dict[int, dict[int, bool]], i: str, j: str, val: bool):
        try:
            assert dp[i]
        except KeyError:
            dp[i] = {}
        try:
            assert dp[i][j]
        except KeyError:
            dp[i][j] = False
        dp[i][j] = val

    def longestPalindrome(self, s: str) -> str:
        if len(s) < 1:           ✅ fixed: returns '' instead of '0'
            return ''

        dp = {}
        longest_palindrome = ''

        # ✅ fixed: base case for length 1
        for i in range(len(s)):
            self.hash_array_set(dp, i, i, True)

        # ✅ unified loop replaces three separate loops
        for str_len in range(len(s) + 1):
            for idx in range(len(s) - str_len):
                i, j = idx, idx + str_len            ← BUG #1: j = idx + str_len (same Bug #4 from submission 1)
                is_pal = (s[i] == s[j]) and (str_len <= 3 or dp[i][j])  ← BUG #2: dp[i][j] should be dp[i+1][j-1]
                                                                             ← BUG #3: str_len<=3 guard fires for wrong actual lengths
                if is_pal:
                    longest_palindrome = s[i:j+1]   ← Issue: no length check, overwrites blindly
                self.hash_array_set(dp, i, j, is_pal)

        return longest_palindrome
      

🔴 Blocking Bugs

Bug #1 — Same `j = idx + str_len` off-by-one from submission 1 BLOCKING

You renamed the variable to str_len but it still isn't the substring length — it's j - idx which equals length - 1. When you write for str_len in range(n+1), you iterate over 0, 1, 2, ..., n, but:

str_len=0 → j=idx, actual substring length = 1 (redundant with base case)
str_len=1 → j=idx+1, actual substring length = 2
str_len=2 → j=idx+2, actual substring length = 3
str_len=3 → j=idx+3, actual substring length = 4

This alone isn't fatal — but it sets up Bug #3 to be catastrophic.

Fix:

j = idx + length - 1 and iterate for length in range(2, n+1)

Bug #2 — Recurrence checks `dp[i][j]` instead of `dp[i+1][j-1]` BLOCKING

This is the most serious error. Your recurrence says:

is_pal = (s[i] == s[j]) and (str_len <= 3 or dp[i][j])  ← checks ITSELF!
Should be:
is_pal = (s[i] == s[j]) and (len <= 3 or dp[i+1][j-1])  ← checks inner substring
        

dp[i][j] is the cell you're currently computing — it hasn't been set yet (or is False from the hash-map default). For any substring where str_len > 3 (actual length ≥ 5), this always evaluates to False, making every palindrome of length ≥ 5 invisible to the algorithm.

Counterexample: "abcba" (length 5). The code checks dp[0][4] which is unset → False. Result: "bcb" instead of "abcba".

Bug #3 — `str_len <= 3` guard fires for wrong actual lengths BLOCKING

Because str_len is really length - 1, the guard str_len <= 3 corresponds to actual substring lengths 2, 3, and 4. This means every length-4 substring with matching outer characters is treated as a palindrome without checking the inner pair — even when the inner pair mismatches.

Counterexample: "abca" (n=4, str_len=3): s[0]==s[3] and 3 <= 3 → True. Result: "abca" reported as palindrome — it's not.

The double hit: Bug #2 kills all palindromes of length ≥ 5 (false negatives). Bug #3 creates false palindromes at exactly length 4 (false positives). The bugs partially mask each other when they shouldn't.

🟡 Design / Code Quality Issues

Issue #4 — Overwrites `longest_palindrome` without checking length

Every time is_pal is True, you blindly overwrite longest_palindrome regardless of whether the new palindrome is actually longer. This works only because str_len increases monotonically (so later palindromes happen to be longer). If the loop order ever changed, or if a shorter palindrome is checked after a longer one within the same iteration, the result would be wrong. A if len(cand) > len(longest_palindrome) guard costs nothing and documents intent.

Issue #5 — `range(len(s) + 1)` includes `str_len=0`

str_len=0 re-checks every single-character substring that was already handled by the base case. It's redundant and makes the loop harder to reason about. A cleaner range: for length in range(2, n+1).

Issue #6 — Same `try/except assert` anti-pattern

Unchanged from submission #1. assert inside try/except to detect missing dict keys remains non-idiomatic and breaks with python -O.

Issue #7 — `hash_array_get` still has unused `val` parameter

And this function is no longer even called — you inlined the lookup with dp[i][j] (which is itself the bug). Dead code signals incomplete refactoring.

Issue #8 — Hash-map approach still adds complexity without benefit

Same concern as submission #1. A 2D list is simpler, faster, and makes indexing mistakes like dp[i][j] vs dp[i+1][j-1] more visually obvious.

🟢 How to Fix (minimal changes to preserve your approach)

Three targeted fixes:

Rename and re-range: iterate for length in range(2, n+1) and set j = idx + length - 1
Fix the recurrence: dp[i+1][j-1] not dp[i][j]
Adjust the guard: length <= 3 (now uses the correct variable)

# Minimally-fixed version of your approach
def longestPalindrome(self, s: str) -> str:
    n = len(s)
    if n == 0:
        return ""

    dp = {}
    start, max_len = 0, 1

    # Base: single chars
    for i in range(n):
        dp.setdefault(i, {})[i] = True

    # Fill by actual substring length (not j-idx)
    for length in range(2, n + 1):
        for idx in range(n - length + 1):
            i, j = idx, idx + length - 1          # ← j = i + (length - 1)

            if s[i] != s[j]:
                dp.setdefault(i, {})[j] = False
            elif length <= 3:                          # ← now uses 'length', not 'str_len'
                dp.setdefault(i, {})[j] = True
            else:
                inner = dp.get(i + 1, {}).get(j - 1, False)  # ← dp[i+1][j-1], NOT dp[i][j]
                dp.setdefault(i, {})[j] = inner

            if dp.get(i, {}).get(j, False) and length > max_len:
                start = idx
                max_len = length

    return s[start:start + max_len]
      

🎯 The pattern you're fighting

You keep hitting the same wall: translating "by increasing length" into correct loop indices. Both submissions have the recurrence right in your head (s[i]==s[j] and inner is palindrome), but the code writes dp[i][j] when it means dp[i+1][j-1], and the loop variable confuses "length" with "j - idx".

Concrete habit: Before writing the loop, write this invariant on a comment line:

# INVARIANT: j - i + 1 == length   (substring has exactly 'length' chars)
# Therefore: j = i + length - 1
        

And triple-check that every recurrence reference is to a strictly shorter interval: dp[i+1][j-1] in this problem, dp[i+1][j] or dp[i][j-1] in others.

▶ Submission #3 — Range tweak (third attempt) 5 bugs 2 issues

Click to expand

Verdict: Crashes on every non-trivial input The range "fix" inverted the bug — now IndexError instead of wrong answer

What you changed from #2: loop now starts at range(2, n+1) (skipping str_len=0,1) and range(n - str_len + 1) (attempting to fix the off-by-one). Neither addresses the root cause, and the +1 introduces an out-of-bounds crash on every non-trivial input.

Your code:

# Base case (unchanged)
for i in range(len(s)):
    self.hash_array_set(dp, i, i, True)

for str_len in range(2, len(s) + 1):              ← BUG A: starts at 2 → skips actual length 2
    for idx in range(len(s) - str_len + 1):    ← BUG B: +1 → last idx gives j = len(s) → IndexError
        i, j = idx, idx + str_len                  ← BUG C: j = idx+str_len (not length-1)
        is_pal = (s[i] == s[j]) and (str_len <= 3 or dp[i][j])  ← BUG D: dp[i][j] → should be dp[i+1][j-1]
                                                     ← BUG E: str_len<=3 fires for wrong actual lengths
        if is_pal:
            longest_palindrome = s[i:j+1]
        self.hash_array_set(dp, i, j, is_pal)

return longest_palindrome
      

🔴 Blocking Bugs

Bug A — `range(2, n+1)` skips all length-2 substrings BLOCKING

Your str_len variable is really j - idx, which equals actual_length - 1:

str_len=0	→	actual length 1 (handled by base case)
str_len=1	→	actual length 2 ← MISSING!
str_len=2	→	actual length 3 (first loop iteration)

"cbbd" (whose only palindrome is "bb", length 2) would return "" — if it didn't crash first.

Bug B — `range(n - str_len + 1)` ⇒ IndexError BLOCKING

With j = idx + str_len, the last iteration gives:

idx_max = (n - str_len + 1) - 1 = n - str_len
j_last  = idx_max + str_len = n    ← valid indices: 0..n-1 → crash!
        

The +1 was an attempt to fix the off-by-one from submission #1, but the real problem is j = idx + str_len (should be idx + str_len - 1). Adding +1 to the range flips the bug from "never reaches the last substring" to "goes past the last valid index."

Bugs C, D, E — Carried over from submission #2 BLOCKING

C: j = idx + str_len — same off-by-one. str_len is j - i, so actual substring length = str_len + 1.
D: dp[i][j] — still checks the cell being computed, not dp[i+1][j-1] (the inner substring).
E: str_len <= 3 guard fires for actual lengths 2,3,4 — still wrong for actual length 4.

🟡 Design Issues

Issue #6 — Base case never initializes `longest_palindrome`

If every palindrome is length 1 (e.g., "abc"), longest_palindrome stays "". Even the single test case that doesn't crash ("a") returns "".

Issue #7 — Still overwrites without length comparison

Unchanged from #2. Relies on loop ordering rather than an explicit len(candidate) > len(current) guard.

🎯 The deeper pattern across all three submissions

All three submissions share the same root cause: you're treating str_len as substring length when it's actually j - i (length − 1). This creates a cascade: the range bound, the base-case guard, and the recurrence all operate on the wrong quantity.

Tweaking ranges and start values won't fix it. You need to rename the variable to match reality and derive j from the invariant:

# INVARIANT: j - i + 1 == length
# Therefore:  j = i + length - 1

for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        dp[i][j] = (s[i] == s[j]) and (length <= 3 or dp[i+1][j-1])
        

Once j is correct, everything collapses into place: the range bound, the guard, and the recurrence all use the same length variable that means exactly what it says.

When you see a substring/subarray problem, ask:

Can the answer for [i..j] be expressed in terms of [i+1..j], [i..j-1], or [i+1..j-1]?
Are the base cases (length 0, 1, or 2) trivial?
Is the recurrence monotonic (always depends on shorter intervals)?

If yes to all three → interval DP, fill by length.

Longest Palindromic Substring Mastering the DP recurrence pattern

📋 Problem Statement

Example 1

Example 2

Constraints

1. What makes a palindrome?

The core insight

2. The recurrence relation

Why this pattern is reusable

3. Interactive DP table walkthrough

4. How to fill the DP table (the traversal order)

The diagonal traversal

5. The complete solution

6. Recognizing this pattern in other problems

7. Submissions — click to expand

Your submitted code:

🔴 Blocking Bugs

Bug #1 — Off-by-one in the outer loop BLOCKING

Fix:

Bug #2 — Variable name typo: longest_palindrom BLOCKING

Bug #3 — Missing self. on hash_array_get BLOCKING

Bug #4 — Wrong j calculation: j = idx + str_len BLOCKING

Fix:

🟡 Design / Code Quality Issues

Issue #4 — Edge case returns wrong sentinel

Issue #5 — No base case for length 1

Issue #6 — Unnecessary special-casing of lengths 2 and 3

The unified approach:

Issue #7 — Anti-pattern: try/except assert for dict defaults

Issue #8 — Type hints are wrong

Issue #9 — Sparse hash-map buys nothing here

🟢 Fixed & Improved Solution

What changed and why:

🎯 Key Takeaway

Your submitted code:

🔴 Blocking Bugs

Bug #1 — Same j = idx + str_len off-by-one from submission 1 BLOCKING

Fix:

Bug #2 — Recurrence checks dp[i][j] instead of dp[i+1][j-1] BLOCKING

Bug #3 — str_len <= 3 guard fires for wrong actual lengths BLOCKING

🟡 Design / Code Quality Issues

Issue #4 — Overwrites longest_palindrome without checking length

Issue #5 — range(len(s) + 1) includes str_len=0

Issue #6 — Same try/except assert anti-pattern

Issue #7 — hash_array_get still has unused val parameter

Issue #8 — Hash-map approach still adds complexity without benefit

🟢 How to Fix (minimal changes to preserve your approach)

Three targeted fixes:

🎯 The pattern you're fighting

Your code:

🔴 Blocking Bugs

Bug A — range(2, n+1) skips all length-2 substrings BLOCKING

Bug B — range(n - str_len + 1) ⇒ IndexError BLOCKING

Bugs C, D, E — Carried over from submission #2 BLOCKING

🟡 Design Issues

Issue #6 — Base case never initializes longest_palindrome

Issue #7 — Still overwrites without length comparison

🎯 The deeper pattern across all three submissions

When you see a substring/subarray problem, ask:

Longest Palindromic Substring
Mastering the DP recurrence pattern

Bug #2 — Variable name typo: `longest_palindrom` BLOCKING

Bug #3 — Missing `self.` on `hash_array_get` BLOCKING

Bug #4 — Wrong `j` calculation: `j = idx + str_len` BLOCKING

Issue #7 — Anti-pattern: `try/except assert` for dict defaults

Bug #1 — Same `j = idx + str_len` off-by-one from submission 1 BLOCKING

Bug #2 — Recurrence checks `dp[i][j]` instead of `dp[i+1][j-1]` BLOCKING

Bug #3 — `str_len <= 3` guard fires for wrong actual lengths BLOCKING

Issue #4 — Overwrites `longest_palindrome` without checking length

Issue #5 — `range(len(s) + 1)` includes `str_len=0`

Issue #6 — Same `try/except assert` anti-pattern

Issue #7 — `hash_array_get` still has unused `val` parameter

Bug A — `range(2, n+1)` skips all length-2 substrings BLOCKING

Bug B — `range(n - str_len + 1)` ⇒ IndexError BLOCKING

Issue #6 — Base case never initializes `longest_palindrome`