Understanding Longest Palindromic Substring: DP Approach Explained

1. Introduction and Core Concepts

The longest palindromic substring problem is a cornerstone of string algorithms and a classic application of dynamic programming. Given a string s, the task is to find the longest contiguous substring of s that reads the same forwards and backwards. Unlike subsequences, which need not be contiguous, a substring must consist of consecutive characters from the original string. For example, in the string "babad", the longest palindromic substrings are "bab" and "aba", both of length 3, while in "cbbd" the answer is "bb".

Understanding palindromes is fundamental because they represent symmetry in sequential data. A palindrome is formally defined as a string where s[i] == s[n-1-i] for all valid indices i. Single characters are trivially palindromes of length 1, and the empty string is often considered a palindrome of length 0. The challenge of the longest palindromic substring lies not in checking if a single string is a palindrome, which can be done in linear time, but in efficiently searching among the O(n²) possible substrings to find the maximum length palindrome without resorting to brute-force enumeration.

This problem matters far beyond coding interviews. It exemplifies the optimal substructure and overlapping subproblems that make dynamic programming (DP) powerful. The DP approach to the longest palindromic substring teaches how to build solutions for larger intervals from solutions for smaller intervals, a pattern that recurs in problems like matrix chain multiplication, optimal binary search trees, and sequence alignment. Mastering this DP formulation provides a mental model for any interval DP problem and sharpens intuition about how to trade time for space by memoizing intermediate results.

Why Dynamic Programming is a Natural Fit

Dynamic programming excels when a problem can be broken down recursively and the same subproblems are solved repeatedly. For palindromes, the key observation is that a substring s[i..j] is a palindrome if and only if its outer characters match (s[i] == s[j]) and its inner substring s[i+1..j-1] is also a palindrome. This creates a direct dependency from a larger interval to a smaller, strictly contained interval. Without memoization, a naive recursive check would re-evaluate the same inner substrings exponentially many times.

The DP approach systematically fills a table that records whether every possible substring is a palindrome. By solving smaller substrings first and reusing those results, we eliminate redundant work. This bottom-up strategy guarantees that when we need to know if s[i+1..j-1] is a palindrome, the answer is already computed and available in O(1) time. This transforms an otherwise O(n³) brute-force solution into an O(n²) solution with clear, predictable performance.

Substrings vs. Subsequences vs. Subarrays

Beginners often confuse substrings with subsequences. A substring requires contiguity, while a subsequence can skip characters. For "abac", "aba" is both a substring and a subsequence, but "aac" is only a subsequence. The longest palindromic subsequence problem has a different DP recurrence and typically allows non-contiguous characters, leading to a different complexity profile. Clarifying this distinction is critical because the DP state definition changes completely: for substrings we care about intervals [i, j], while for subsequences we often consider the same interval but with different transition rules that allow skipping characters.

2. How It Works

The DP solution for the longest palindromic substring revolves around a two-dimensional boolean table dp where dp[i][j] is True if the substring starting at index i and ending at index j (inclusive) is a palindrome, and False otherwise. The table has dimensions n x n where n is the length of the input string. Only the upper triangle of the table is meaningful since we always maintain i <= j. The goal is to fill this table in order of increasing substring length and track the longest interval where dp[i][j] is true.

The recurrence relation is elegant and has three cases. First, every substring of length 1 is a palindrome, so dp[i][i] = True for all i. Second, for substrings of length 2, dp[i][i+1] = (s[i] == s[i+1]). Third, for substrings of length 3 or greater (j - i >= 2), dp[i][j] = (s[i] == s[j] and dp[i+1][j-1] == True). This third case embodies the optimal substructure: the palindromic status of the outer interval depends entirely on the outer characters and the status of the inner interval.

The order of filling the table is crucial. If we filled row by row, we might query dp[i+1][j-1] before it has been computed. Instead, we fill by substring length, also called gap or diagonal order. We start with gap 0 (length 1), then gap 1 (length 2), then gap 2 (length 3), and so on up to gap n-1 (the entire string). This guarantees that all smaller intervals are resolved before larger intervals that depend on them. While filling, we maintain two variables, start and max_len, updating them whenever we find a palindrome longer than the current maximum.

The DP State Transition in Detail

Consider the substring s[i..j] with length L = j - i + 1. If L == 1, the answer is trivially true. If L == 2, we only need to compare two characters. For L > 2, the condition s[i] == s[j] is necessary but not sufficient; the inner substring must also be a palindrome. For example, "abca" has matching outer characters 'a' and 'a', but "bc" is not a palindrome, so "abca" is not a palindrome. Conversely, "abba" has outer 'a' == 'a' and inner "bb" is a palindrome, so "abba" is a palindrome. The DP table captures this logic precisely without re-scanning the inner substring.

This recurrence also handles even and odd length palindromes uniformly. Odd-length palindromes have a single center character (like "racecar" centered at 'e'), while even-length palindromes have a center between two characters (like "abba" centered between the two 'b's). Because the DP checks all intervals regardless of parity, both types are discovered naturally without needing separate logic, which is an advantage over some center-expansion implementations that must handle both cases explicitly.

Visualizing the DP Table

Imagine a matrix where rows represent start indices i and columns represent end indices j. The main diagonal corresponds to single characters. The superdiagonal (one step above the main diagonal) corresponds to length-2 substrings. Each subsequent diagonal upwards corresponds to longer substrings. A True entry indicates a palindromic interval. The longest palindromic substring corresponds to the farthest True entry from the main diagonal. This geometric view helps debug DP implementations: if you print the table, palindromes appear as true values clustered along diagonals, and you can visually trace how larger palindromes build upon smaller ones.

3. Implementation

Implementing the DP approach in Python requires careful handling of indices, base cases, and table initialization. The following examples progress from a brute-force baseline to a fully optimized DP solution with detailed comments. All code is written for clarity and correctness, with explicit handling of edge cases such as empty strings and single-character inputs.

The first implementation shows the naive brute-force method for comparison. It enumerates all O(n²) substrings and checks each for palindromicity in O(n) time, resulting in O(n³) total time. While inefficient, it serves as a correctness oracle for testing the DP solution.

# Brute-force baseline: O(n^3) time, O(1) extra space
def longest_palindrome_brute(s: str) -> str:
    n = len(s)
    if n <= 1:
        return s
    
    longest = s[0]  # at least one character is a palindrome
    
    # Enumerate all substrings s[i:j+1]
    for i in range(n):
        for j in range(i, n):
            substr = s[i:j+1]
            # Check palindrome by reversing
            is_pal = substr == substr[::-1]
            if is_pal and len(substr) > len(longest):
                longest = substr
    return longest

# Example: longest_palindrome_brute("babad") returns "bab" or "aba"

The canonical DP implementation follows. It initializes an n x n boolean table, fills it by increasing gap length, and tracks the longest palindrome found. Note the use of <= and > which must be escaped as <= and > in HTML contexts, and the careful order of gap iteration.

def longest_palindromic_substring_dp(s: str) -> str:
    """
    DP approach for longest palindromic substring.
    dp[i][j] == True if s[i:j+1] is a palindrome.
    Time: O(n^2), Space: O(n^2)
    """
    n = len(s)
    if n <= 1:
        return s

    # dp[i][j] will be True if substring s[i:j+1] is palindrome
    dp = [[False] * n for _ in range(n)]
    
    start = 0  # start index of longest palindrome found
    max_len = 1  # length of longest palindrome (single char)

    # Base case: substrings of length 1 (gap = 0)
    for i in range(n):
        dp[i][i] = True

    # Base case: substrings of length 2 (gap = 1)
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_len = 2

    # Fill for lengths >= 3 (gap >= 2)
    # gap = j - i
    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            # Check outer chars and inner substring
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                # Update longest if this palindrome is longer
                if gap + 1 > max_len:
                    start = i
                    max_len = gap + 1
    
    return s[start:start + max_len]

This next variant not only returns the longest palindromic substring but also counts all palindromic substrings and optionally prints the DP table for debugging. It is useful for understanding how the table evolves and for solving the related problem of counting palindromic substrings, which is a common follow-up interview question.

def longest_palindrome_dp_with_count(s: str, debug: bool = False) -> tuple:
    """
    Returns (longest_palindrome, count_of_all_palindromic_substrings, dp_table)
    Demonstrates how DP table can be reused for counting.
    """
    n = len(s)
    if n == 0:
        return ("", 0, [])
    if n == 1:
        return (s, 1, [[True]])

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

    for i in range(n):
        dp[i][i] = True
        count += 1

    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            count += 1
            if max_len < 2:
                start, max_len = i, 2

    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                count += 1
                if gap + 1 > max_len:
                    start = i
                    max_len = gap + 1

    if debug:
        # Print DP table: 1 for True, 0 for False
        for row in dp:
            print(" ".join("1" if x else "0" for x in row))

    longest = s[start:start + max_len]
    return (longest, count, dp)

For production code, you may want to handle Unicode, case-insensitivity, or to reconstruct all longest palindromes when ties exist. The following implementation collects all maximal palindromes and demonstrates input sanitization, which is often overlooked in textbook examples.

def all_longest_palindromes(s: str, case_sensitive: bool = True) -> list:
    """
    Returns all distinct longest palindromic substrings.
    Handles case-insensitive mode and Unicode correctly.
    """
    if not case_sensitive:
        # Use lowercased version for DP but map back to original indices
        # For simplicity, we operate on lowercased string here
        s_proc = s.lower()
    else:
        s_proc = s

    n = len(s_proc)
    if n <= 1:
        return [s]

    dp = [[False] * n for _ in range(n)]
    max_len = 1
    # Store start indices of longest palindromes
    result_starts = [0]

    for i in range(n):
        dp[i][i] = True

    for i in range(n - 1):
        if s_proc[i] == s_proc[i + 1]:
            dp[i][i + 1] = True
            if max_len < 2:
                max_len = 2
                result_starts = [i]
            elif max_len == 2:
                result_starts.append(i)

    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            if s_proc[i] == s_proc[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                cur_len = gap + 1
                if cur_len > max_len:
                    max_len = cur_len
                    result_starts = [i]
                elif cur_len == max_len:
                    result_starts.append(i)

    # Deduplicate by actual substring content from original string
    seen = set()
    results = []
    for st in result_starts:
        pal = s[st:st + max_len]
        if pal not in seen:
            seen.add(pal)
            results.append(pal)
    return results

# Example: all_longest_palindromes("babad") -> ["bab", "aba"] (order may vary)
# Example: all_longest_palindromes("AbBa", case_sensitive=False) -> ["AbBa"]

4. Step-by-Step Example

To solidify the DP mechanics, let us walk through the complete execution for the string s = "ababa", which has length n = 5. The string contains multiple palindromes, and its longest palindromic substring is the entire string "ababa" itself, length 5. This example is ideal because it includes overlapping palindromes of both odd and even lengths and demonstrates how the DP table builds from small gaps to large gaps.

We initialize a 5x5 table dp with all False. We set start = 0 and max_len = 1. The indices are 0:a, 1:b, 2:a, 3:b, 4:a. The table will be filled diagonal by diagonal. For clarity, we label gaps as gap = j - i, which equals length - 1.

Step 1: Gap 0 (Length 1). Every single character is a palindrome. We set dp[0][0], dp[1][1], dp[2][2], dp[3][3], dp[4][4] = True. The table now has True on the main diagonal. max_len remains 1, start remains 0. These entries will be used as base cases for length-3 substrings.

Step 2: Gap 1 (Length 2). Check all pairs: "ab" (0,1): 'a' != 'b' so False; "ba" (1,2): 'b' != 'a' False; "ab" (2,3): False; "ba" (3,4): False. No length-2 palindromes exist. dp superdiagonal remains False. max_len stays 1. This is expected because the string alternates characters.

Step 3: Gap 2 (Length 3). Now we use the recurrence dp[i][j] = s[i]==s[j] and dp[i+1][j-1]. For (0,2): s[0]='a', s[2]='a' match and dp[1][1] is True, so dp[0][2]=True ("aba"). Similarly (1,3): s[1]='b', s[3]='b' and dp[2][2] True => True ("bab"). (2,4): s[2]='a', s[4]='a' and dp[3][3] True => True ("aba"). We found three palindromes of length 3. We update max_len = 3 and start = 0 (first found). At this point the longest is "aba".

Step 4: Gap 3 (Length 4). Check (0,3): s[0]='a', s[3]='b' mismatch => False regardless of dp[1][2] (which is False). (1,4): s[1]='b', s[4]='a' mismatch => False. No length-4 palindromes. max_len remains 3.

Step 5: Gap 4 (Length 5). Check (0,4): s[0]='a', s[4]='a' match and dp[1][3] is True (from previous step, "bab" is palindrome), so dp[0][4] = True. The entire string "ababa" is a palindrome. We update max_len = 5 and start = 0. The algorithm terminates and returns s[0:5] = "ababa".

DP Table Snapshot for "ababa"

After completion, the upper triangle of the DP table looks like this (T=True, F=False, - indicates i > j unused):

• Row 0: [T, F, T, F, T]
• Row 1: [-, T, F, T, F]
• Row 2: [-, -, T, F, T]
• Row 3: [-, -, -, T, F]
• Row 4: [-, -, -, -, T]

Notice the pattern: True entries appear on alternating diagonals, reflecting the alternating character structure. The farthest True from the diagonal is at (0,4), confirming the longest palindrome spans the whole string. Tracing back from (0,4) to (1,3) to (2,2) shows the recursive chain that proves "ababa" is a palindrome because "bab" is, and "bab" is because "a" is.

What If the String Was "cbbd"?

For contrast, consider "cbbd" (n=4). Gap 0: all True. Gap 1: (0,1) 'c'!='b' False, (1,2) 'b'=='b' True => max_len=2 start=1, (2,3) 'b'!='d' False. Gap 2: (0,2) 'c'!='b' False, (1,3) 'b'!='d' False. Gap 3: (0,3) 'c'!='d' False. Result is s[1:3]="bb". This example shows how the DP correctly identifies even-length palindromes without special casing and how max_len only updates when a strictly longer palindrome is found, preserving the first longest if ties exist.

5. Complexity Analysis

Analyzing the DP approach requires examining both time and space costs across different input characteristics. While the asymptotic bounds are well-known, understanding best, average, and worst-case behavior helps in selecting the right algorithm for production workloads and in predicting performance on real data distributions.

The DP algorithm's time complexity is dominated by the nested loops that fill the table. There are O(n²) entries to fill (specifically n*(n+1)/2 entries in the upper triangle), and each entry is computed in O(1) time using the precomputed inner result. The outer loop iterates over gaps from 0 to n-1, and the inner loop iterates over start indices. Therefore, total time is Θ(n²) in all cases. There is no early exit that changes asymptotic complexity, although in practice the inner condition s[i]==s[j] fails quickly for strings with diverse characters, reducing constant factors.

Space complexity is O(n²) for the full DP table of booleans. Each entry is a single bit conceptually, but in Python a list of lists of booleans uses significantly more memory due to object overhead. For a string of length 5000, the table would require ~25 million booleans, which is ~25 MB if bit-packed but can exceed 200 MB in Python. This quadratic memory is the primary drawback of the DP approach compared to O(1) space alternatives like center expansion.

Best, average, and worst cases for time are all O(n²) because the table must be fully populated regardless of input. However, the number of palindromic substrings discovered varies: a string of all identical characters like "aaaaa" yields O(n²) palindromic substrings (every interval is a palindrome), while a string with all distinct characters like "abcdef" yields only n palindromes (the single characters). This affects how often max_len is updated but not the total work.

Memory Optimization Considerations

The O(n²) space can be optimized if we only need the length of the longest palindrome and not the table itself for reconstruction. However, unlike some DP problems (e.g., Fibonacci), the recurrence dp[i][j] depends on dp[i+1][j-1], which is not in the previous row but diagonally offset. This makes simple rolling-array optimization to O(n) more complex, though it is possible to store only two diagonals at a time if we only need to know existence and not reconstruct the substring. In practice, most implementations keep the full table for clarity.

For very large strings (n > 10,000), the quadratic time and space become prohibitive. In such regimes, Manacher's algorithm with O(n) time and O(n) space is preferable. The DP approach remains the pedagogical gold standard and is perfectly adequate for interview constraints where n is typically ≤ 1000, as well as for moderate-sized strings in bioinformatics or text processing where clarity and correctness outweigh extreme scalability.

6. Variations and Optimizations

While the classic O(n²) DP table is the most taught version, several variations and optimizations address its limitations in space, constant factors, and functionality. Understanding these variants demonstrates deeper mastery and prepares you to adapt the core idea to related problems.

One common optimization is to use a bitset or array of integers to store the DP table more compactly. In languages like Python, using the array('b') or bytearray can reduce memory overhead. Another technique is to store only the upper triangle as a list of lists of varying lengths, saving roughly half the memory. For example, row i only needs n - i entries. While this complicates indexing, it halves memory usage and improves cache locality.

A more algorithmic optimization is to prune the search. If the remaining possible substring length (n - i) is less than the current max_len, we can skip that row entirely because we cannot find a longer palindrome starting at i. Similarly, within a gap iteration, if gap + 1 <= max_len, that gap cannot improve the answer, though we still need to fill the table for correctness of larger gaps. These pruning strategies do not change worst-case complexity but can significantly speed up average cases on strings with early long palindromes.

Bottom-Up vs. Top-Down Memoization

The bottom-up tabulation described so far is iterative. An alternative is top-down recursion with memoization. Define a recursive function is_pal(i, j) that returns True if s[i..j] is palindrome, using memoization to cache results. The recurrence is identical, but the computation is demand-driven and uses recursion stack space O(n). While elegant, top-down can incur recursion depth limits in Python for long strings and may have higher constant factors due to function call overhead. However, it can be more efficient when the input has few palindromic substrings because it only explores intervals that are actually queried, potentially avoiding filling the entire table.

Counting and Enumerating All Palindromes

The DP table naturally solves two related problems: counting total palindromic substrings and enumerating all distinct palindromes. After filling the table, the count is simply the number of True entries. Enumeration requires scanning the table and collecting substrings where dp[i][j] is True. This is useful for applications like finding all palindromic motifs in DNA sequences. The same table can also be adapted to find the longest palindromic subsequence (by changing the recurrence to allow skipping characters) or to find palindromic partitions for the palindrome partitioning problem.

Space-Optimized DP with Diagonal Storage

Advanced implementations reduce space to O(n) by observing that to compute gap g, we only need gap g-2. By keeping two one-dimensional arrays representing the previous two diagonals, we can compute the current diagonal. However, reconstructing the actual longest substring (not just its length) then requires additional bookkeeping to remember where the longest palindrome started and ended, since we no longer have the full table to trace back. This trade-off is worthwhile in memory-constrained environments like embedded systems or when processing streaming text.

7. Real-World Applications

Although finding the longest palindromic substring may seem like a purely academic exercise, palindrome detection and symmetric substring analysis have surprising real-world relevance across multiple domains. The DP approach, with its ability to enumerate all palindromic substrings, is particularly valuable when not just the longest but the full distribution of palindromes matters.

In bioinformatics, DNA and RNA sequences contain palindromic structures that are biologically significant. Restriction enzyme recognition sites are often palindromic (e.g., "GAATTC" reads the same on the complementary strand), and hairpin loops in RNA secondary structure involve palindromic or near-palindromic sequences. Finding the longest palindromic substring helps identify potential binding sites, CRISPR targets, and structural motifs. The DP table's ability to find all palindromes allows researchers to catalog inverted repeats across a genome, which are implicated in gene regulation and genome instability.

In natural language processing and text analysis, palindromes are used for data cleaning, plagiarism detection, and linguistic pattern discovery. While natural language rarely contains long palindromes, the algorithm's interval DP framework is reused for more general symmetric pattern matching, such as detecting repeated phrases or mirrored structures in poetry and wordplay. The same DP logic extends to finding the longest common substring or longest repeated substring, which are critical for deduplication and compression.

In cybersecurity and data validation, palindromic checks serve as lightweight integrity tests. Some hashing and checksum algorithms exploit palindromic properties to detect tampering. In database systems, palindrome-like queries can optimize string indexing: knowing the distribution of palindromic substrings helps estimate selectivity for LIKE queries with wildcards. In networking, palindromic payloads are sometimes used as test patterns for verifying that middleboxes do not corrupt data in transit.

From Theory to Production

In production systems handling large strings, the O(n²) DP is often replaced by Manacher's algorithm for performance, but the DP remains valuable for prototyping and for cases where all palindromes are needed, not just the longest. For example, a web server log analyzer might use the DP to find all palindromic request IDs to detect anomalous mirrored traffic patterns. The clarity of the DP table also makes it easier to audit and extend with custom constraints, such as allowing one mismatch (longest palindromic substring with one edit) or handling case-insensitive Unicode.

8. Comparison with Alternatives

The DP approach is one of several strategies for finding the longest palindromic substring. Each method trades off time, space, implementation complexity, and functionality. Understanding these trade-offs is essential for choosing the right tool for a given constraint, whether you are in a coding interview with limited time or building a high-throughput genomic pipeline.

The brute-force approach is the simplest to implement but the slowest, checking every substring by direct comparison. The expand-around-center approach is the most popular interview solution due to its O(1) space and O(n²) time with simple code. Manacher's algorithm is the theoretical optimum with O(n) time but is significantly more complex to implement correctly. The DP approach sits in the middle: it is more systematic than center expansion and provides the full palindrome distribution, but it pays a quadratic space cost.

Choosing between them depends on requirements. If you only need the longest palindrome and memory is tight, expand-around-center is ideal. If you need to count all palindromes or answer many queries about arbitrary intervals being palindromes, the DP table is invaluable because it answers any interval query in O(1) after O(n²) preprocessing. If you need optimal linear time for very long strings, Manacher's is the only choice.

When to Prefer DP Over Center Expansion

Prefer DP when you need to answer multiple queries about palindromicity of arbitrary substrings after preprocessing, when you need to count or enumerate all palindromic substrings, or when you are teaching or demonstrating interval DP concepts. The DP table provides a complete oracle for any interval, which center expansion does not without re-expanding. For example, if a follow-up question asks for the number of palindromic substrings or the longest palindromic subsequence, the DP mindset transfers directly, whereas center expansion does not.

Prefer expand-around-center when space is constrained or when you only need the single longest palindrome and want the simplest correct solution under interview pressure. Manacher's should be reserved for cases where linear time is a hard requirement and you have thoroughly tested the implementation, as its transformed string and mirror logic are error-prone under time constraints.

9. Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing the DP solution. Awareness of these pitfalls and adherence to best practices can mean the difference between a correct O(n²) solution and a buggy or inefficient one that fails on edge cases.

One of the most frequent mistakes is incorrect table filling order. Filling row-by-row instead of by gap length causes the algorithm to read dp[i+1][j-1] before it is computed, leading to false negatives where longer palindromes are missed. Always iterate by gap or length, not by row and column independently. A related mistake is off-by-one errors in gap loops: the outer loop should run for gap in range(2, n) and the inner loop for i in range(n - gap) with j = i + gap. Using range(n) for both loops will cause index out-of-bounds or incomplete filling.

Another common error is mishandling base cases. Forgetting to initialize length-2 palindromes separately before the main loop will cause length-3 palindromes to be incorrectly evaluated, since they depend on length-1 entries but the recurrence for length-3 assumes the inner length-1 is already True. Some implementations try to handle length-2 inside the general recurrence with a condition like j - i < 3, which works but must be written carefully to avoid logical errors.

Memory and Python-specific pitfalls include using [[False]*n]*n to initialize the DP table, which creates n references to the same row object, so updating one row updates all rows. Always use a list comprehension [[False]*n for _ in range(n)]. Additionally, failing to handle empty string and single-character inputs at the start leads to index errors when accessing s[0] or initializing the table with n=0.

Best Practices for Robust Implementation

• Validate inputs early: Check for None, empty string, and non-string types. Return early for n <= 1 to avoid unnecessary table allocation.
• Use gap-based iteration: Document why you iterate by gap and add comments like # gap = j - i to make the order explicit for reviewers.
• Track start and max_len, not the substring itself: Building substrings inside the loop via slicing creates O(n) copies each time, increasing time to O(n³). Track indices and slice once at the end.
• Test with diverse cases: Include tests for "a", "", "ab", "aa", "aba", "abba", "abcba", "abacdfgdcaba", "aaaa", and a string with no palindrome longer than 1 like "abcdef". Also test Unicode and case sensitivity if applicable.
• Consider space vs. clarity trade-offs: For interview code, prefer the clear O(n²) table over a convoluted O(n) diagonal optimization unless space is explicitly constrained. Clarity is often valued over micro-optimization.
• Escape HTML-sensitive characters in code display: When rendering code in HTML articles, ensure < and > are escaped as < and > to prevent broken markup, especially in comparisons like i < n and j - i > max_len.

Debugging Tips

If your DP returns a palindrome that is too short, print the DP table for a small input like "ababa" and verify that True entries appear where expected. If you see False where True should be, check the condition s[i] == s[j] and dp[i+1][j-1] and ensure dp[i+1][j-1] was already computed. If you get an IndexError, verify loop bounds: i + gap must be < n. Using a debugger or adding assertions like assert 0 <= i <= j < n inside the inner loop can catch boundary violations early.

10. Interview Questions

The longest palindromic substring is a staple of technical interviews, often used to assess understanding of dynamic programming, string manipulation, and complexity analysis. Interviewers frequently extend the core problem with follow-ups that test adaptability. Below are common questions and how to approach them using the DP foundation.

Q1: Implement the DP solution and analyze its complexity. Can you optimize space?

Expected answer: Provide the O(n²) time and O(n²) space DP implementation as shown in Section 3, explain the recurrence dp[i][j] = s[i]==s[j] and dp[i+1][j-1], and describe gap-based filling. For space optimization, discuss that we only need the previous diagonal to compute the current one, so we can reduce to O(n) by storing two arrays, but reconstruction becomes harder. Mention that expand-around-center achieves O(1) space with the same time, and Manacher's achieves O(n) time. This question tests whether you understand both the algorithm and its trade-offs, not just memorization.

Q2: Count the total number of palindromic substrings in a string.

This is a direct extension of the DP table. After filling dp, the answer is the count of True entries. Alternatively, you can count during filling: increment a counter whenever dp[i][j] becomes True. For "aaa", the answer is 6: "a" (3 times), "aa" (2 times), "aaa" (1 time). The DP solution does this in O(n²) time and space, while the center expansion also does it in O(n²) time but O(1) space by expanding and counting. Discuss both and note that the DP table also lets you enumerate them. Edge case: ensure you count single characters.

Q3: How would you find the longest palindromic subsequence (not substring)?

Clarify the difference: subsequence need not be contiguous. The DP for subsequence uses a similar table but with a different recurrence: if s[i]==s[j], then dp[i][j] = dp[i+1][j-1] + 2, else dp[i][j] = max(dp[i+1][j], dp[i][j-1]). The table is still filled by gap, but the meaning of dp[i][j] is the length of the longest palindromic subsequence in s[i..j]. For "bbbab", the longest palindromic substring is "bbb" (length 3) but the longest palindromic subsequence is "bbbb" (length 4). This tests whether you can adapt interval DP to a related problem and not confuse the two recurrences.

Q4: What if you are allowed to change at most k characters to make a substring palindrome? Find the longest substring that can be made palindrome with ≤ k changes.

This generalizes the palindromic condition. Define dp[i][j] as the minimum changes needed to make s[i..j] palindrome. Recurrence: if s[i]==s[j], dp[i][j]=dp[i+1][j-1], else dp[i][j]=dp[i+1][j-1]+1. Base cases: dp[i][i]=0, dp[i][i+1]=0 if s[i]==s[i+1] else 1. After filling, find the longest interval where dp[i][j] <= k. This is O(n²) time and space. Alternatively, use center expansion with a mismatch budget. This question tests ability to extend DP state to include cost.

Q5: How do you handle very long strings (n = 10⁶) where O(n²) is too slow?

For n=10⁶, O(n²) is infeasible (10¹² operations). The correct answer is Manacher's algorithm, which finds the longest palindromic substring in O(n) time and O(n) space by maintaining a radius array and exploiting mirror properties to avoid recomputation. Explain the transformation that inserts '#' between characters to handle even/odd uniformly, and the use of a center and right boundary to reuse previously computed palindromes. If you cannot recall Manacher's perfectly, propose expand-around-center with early pruning or suffix array approaches, but acknowledge that true linear time requires Manacher's. This tests awareness of scalability limits and knowledge of advanced string algorithms.

Preparing for these questions involves not just coding the DP but being able to whiteboard the table for a small example, derive the recurrence from first principles, and discuss trade-offs articulately. Practice writing the DP from scratch without referencing notes, and always test with "babad", "cbbd", "", "a", and "ac" to cover odd, even, empty, and no-palindrome cases.