Solving Longest Palindromic Subsequence with Dynamic Programming

1. Introduction and Core Concepts

The longest palindromic subsequence problem is a classic dynamic programming challenge that asks a deceptively simple question: given a string, what is the longest subsequence that reads the same forwards and backwards? Unlike a substring, a subsequence does not need to be contiguous. You can delete characters without reordering the remaining ones, and the goal is to keep as many characters as possible while achieving palindrome symmetry.

For example, consider the string "BBABCBCAB". Its longest palindromic subsequence is "BABCBAB" or "BACBCAB" with length 7. The string "agbdba" has a longest palindromic subsequence of "abdba" with length 5. Understanding this distinction between substring and subsequence is critical. The longest palindromic substring of "agbdba" is "aba" or "ada" style palindromes of length 3, which is a different problem with different optimal substructure. The subsequence version allows gaps, which makes it more flexible and applicable to problems where insertions and deletions are allowed.

The longest palindromic subsequence matters far beyond coding interviews. It is a foundational example of optimal substructure and overlapping subproblems, the two hallmarks of dynamic programming. It is directly reducible to the Longest Common Subsequence (LCS) problem, connects to edit distance and sequence alignment, and serves as a gateway to understanding how to optimize recursive solutions that would otherwise explode exponentially. Mastering it teaches you how to define DP states over intervals, how to handle two-pointer decisions on string boundaries, and how to reconstruct an actual solution from a DP table, not just compute its length.

Subsequence vs. Substring vs. Subarray

A subarray or substring requires contiguity, while a subsequence only preserves order. This difference completely changes the algorithmic approach. For substrings, center expansion or Manacher's algorithm can find palindromes in linear time. For subsequences, we must consider non-local dependencies, which is why dynamic programming over intervals is necessary.

The formal definition helps: A sequence S' is a subsequence of S if S' can be derived from S by deleting zero or more characters without changing the order of the remaining characters. A palindrome is a sequence that equals its reverse. Therefore, the longest palindromic subsequence of S is the maximum-length sequence P such that P is a subsequence of S and P == reverse(P).

Why This Problem Is Ideal for Dynamic Programming

The longest palindromic subsequence exhibits both optimal substructure and overlapping subproblems. The optimal solution for the interval [i, j] can be built from optimal solutions for smaller intervals like [i+1, j], [i, j-1], and [i+1, j-1]. A naive recursive solution will recompute the same intervals exponentially many times. Dynamic programming eliminates this redundancy by storing interval results and reusing them, reducing an O(2^n) brute force search to O(n^2) time.

2. How It Works

The core insight behind the dynamic programming solution is to define the state as the answer for a substring defined by its endpoints. Let dp[i][j] represent the length of the longest palindromic subsequence within the substring s[i..j] inclusive. Our goal is to compute dp[0][n-1] for a string of length n. The recurrence relation emerges from comparing the characters at the two ends of the interval.

There are two cases to consider for any interval [i, j]. If the characters at the boundaries match, i.e., s[i] == s[j], then those two characters can both be part of the palindrome. The best we can do is to take them and add the optimal solution for the inner interval [i+1, j-1]. So dp[i][j] = dp[i+1][j-1] + 2. If the characters do not match, they cannot both be the outermost characters of the same palindromic subsequence. We must discard one of them, so the answer is the better of the two possibilities: dropping the left character or dropping the right character. Thus dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

This recurrence naturally suggests a bottom-up filling order. The base cases are intervals of length 1, where dp[i][i] = 1, because a single character is always a palindrome of length 1. Intervals of length 2 are handled by the recurrence: if s[i] == s[i+1], dp[i][i+1] = 2, otherwise 1. For longer intervals, we need the results of shorter intervals, so we fill the table by increasing interval length or by iterating i from bottom to top and j from left to right.

The LCS Connection

A powerful alternative viewpoint is that the longest palindromic subsequence of s is exactly the Longest Common Subsequence of s and its reverse, reverse(s). Since a palindromic subsequence reads the same forwards and backwards, it must appear as a common subsequence between the string and its reversal. This equivalence means any LCS algorithm can solve the longest palindromic subsequence problem. While conceptually elegant, the interval DP is often more intuitive and slightly more space-efficient because it works directly on one string without explicitly constructing the reversed copy.

Optimal Substructure in Detail

To prove optimal substructure, consider an optimal palindromic subsequence P for s[i..j]. If s[i] == s[j] and both are used in P, then removing them yields an optimal solution for s[i+1..j-1]. If they are not both used, then P must be optimal for either s[i+1..j] or s[i..j-1]. No other structure is possible, which is why the recurrence covers all cases. This property guarantees that building solutions from smaller intervals is safe and will yield a globally optimal result.

Overlapping Subproblems

A naive recursion branches into two or three subproblems at each step, leading to a recursion tree where the same interval [i, j] is solved many times via different paths. For example, solving [0, n-1] when s[0] != s[n-1] requires solving both [1, n-1] and [0, n-2], both of which in turn require solving [1, n-2]. This duplication grows exponentially. Memoization or tabulation ensures each of the O(n^2) distinct intervals is computed exactly once.

3. Implementation

Implementing the longest palindromic subsequence can be done in several ways, each illustrating a different dynamic programming technique. We will explore four approaches: pure recursion to show the baseline, top-down memoization, bottom-up tabulation, and space-optimized tabulation. All examples use Python and focus on clarity and correctness.

The recursive baseline is essential for understanding the recurrence but is impractical for strings longer than about 25 characters. Memoization adds a cache to make it efficient, while tabulation builds the table iteratively and is often preferred in interviews for its predictable performance and ability to reconstruct the subsequence. The space-optimized version reduces memory from O(n^2) to O(n) when only the length is needed.

Approach 1: Pure Recursion (Exponential)

def lps_recursive(s, i, j):
    # Base cases: single character is palindrome of length 1
    if i == j:
        return 1
    # Base case: empty interval
    if i > j:
        return 0
    # If first and last characters match, include both
    if s[i] == s[j]:
        return 2 + lps_recursive(s, i + 1, j - 1)
    else:
        # Otherwise, try dropping one end and take the maximum
        left = lps_recursive(s, i + 1, j)
        right = lps_recursive(s, i, j - 1)
        return left if left > right else right

# Example usage:
# s = "BBABCBCAB"
# print(lps_recursive(s, 0, len(s) - 1))  # Output: 7

Approach 2: Top-Down Memoization

def lps_memo(s):
    n = len(s)
    memo = [[-1] * n for _ in range(n)]

    def helper(i, j):
        if i > j:
            return 0
        if i == j:
            return 1
        if memo[i][j] != -1:
            return memo[i][j]
        if s[i] == s[j]:
            memo[i][j] = 2 + helper(i + 1, j - 1)
        else:
            a = helper(i + 1, j)
            b = helper(i, j - 1)
            memo[i][j] = a if a > b else b
        return memo[i][j]

    return helper(0, n - 1)

# This version runs in O(n^2) time and O(n^2) space
# Recursion depth is O(n), which is safe for n < 1000 in Python

Approach 3: Bottom-Up Tabulation with Reconstruction

def lps_tabulation(s):
    n = len(s)
    if n == 0:
        return 0, ""
    # dp[i][j] = length of LPS in s[i..j]
    dp = [[0] * n for _ in range(n)]

    # Base case: single characters
    for i in range(n):
        dp[i][i] = 1

    # Fill table 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]:
                if length == 2:
                    dp[i][j] = 2
                else:
                    dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                a = dp[i + 1][j]
                b = dp[i][j - 1]
                dp[i][j] = a if a > b else b

    # Reconstruct one LPS by backtracking
    i, j = 0, n - 1
    left_part = []
    right_part = []
    while i <= j:
        if i == j:
            left_part.append(s[i])
            break
        elif s[i] == s[j]:
            left_part.append(s[i])
            right_part.append(s[j])
            i += 1
            j -= 1
        elif dp[i + 1][j] >= dp[i][j - 1]:
            i += 1
        else:
            j -= 1

    lps_str = "".join(left_part) + "".join(reversed(right_part))
    return dp[0][n - 1], lps_str

# Example: lps_tabulation("BBABCBCAB") returns (7, "BABCBAB")

Approach 4: Space-Optimized DP (Length Only)

def lps_space_optimized(s):
    n = len(s)
    if n == 0:
        return 0
    # Only need previous row, so we use 1D array
    dp = [0] * n

    for i in range(n - 1, -1, -1):
        new_dp = [0] * n
        new_dp[i] = 1
        prev_diag = 0  # stores dp[i+1][j-1] from previous iteration
        for j in range(i + 1, n):
            temp = new_dp[j]  # will become prev_diag next iteration
            # Actually need dp[j] from previous i+1 row
            # Let's use classic 1D optimization with careful ordering
            if s[i] == s[j]:
                new_dp[j] = prev_diag + 2
            else:
                a = dp[j]      # dp[i+1][j]
                b = new_dp[j - 1]  # dp[i][j-1]
                new_dp[j] = a if a > b else b
            prev_diag = temp
        dp = new_dp

    return dp[n - 1]

# Alternative simpler O(n^2) space but O(n) extra is also common:
# Use LCS with reversed string and two rows
def lps_via_lcs(s):
    rev = s[::-1]
    n = len(s)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if s[i - 1] == rev[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                a = prev[j]
                b = curr[j - 1]
                curr[j] = a if a > b else b
        prev, curr = curr, prev
    return prev[n]

4. Step-by-Step Example

Let us walk through the bottom-up tabulation for the string s = "BBABCBCAB" is too large for a manual table, so we will use a smaller illustrative example: s = "agbdba" with n = 6. The longest palindromic subsequence here is "abdba" with length 5. We will build the dp table step by step to see how the recurrence fills in the answer.

We initialize a 6x6 table where dp[i][i] = 1 for all i. All entries where i > j are irrelevant and remain 0. We then iterate by substring length from 2 to 6. For length 2, we compare each adjacent pair: "ag" (a != g) gives max(dp[1][1], dp[0][0]) = 1, "gb" gives 1, "bd" gives 1, "db" gives 1, "ba" gives 1. Only pairs with equal characters would give 2, but none of these adjacent pairs match.

For length 3, we examine intervals like [0,2] = "agb": s[0]=a, s[2]=b, they differ, so dp[0][2] = max(dp[1][2]=1, dp[0][1]=1) = 1. Interval [1,3] = "gbd": g != d, so max(1,1)=1. Interval [2,4] = "bdb": s[2]=b, s[4]=b, they match, so dp[2][4] = dp[3][3] + 2 = 1 + 2 = 3, which corresponds to "bdb". Interval [3,5] = "dba": d != a, so 1. This is where the first non-trivial palindrome emerges.

Filling Longer Intervals

For length 4, interval [0,3] = "agbd": a != d, so max(dp[1][3]=1, dp[0][2]=1)=1. Interval [1,4] = "gbdb": g != b, so max(dp[2][4]=3, dp[1][3]=1)=3. Interval [2,5] = "bdba": b != a, so max(dp[3][5]=1, dp[2][4]=3)=3. For length 5, interval [0,4] = "agbdb": a != b, so max(dp[1][4]=3, dp[0][3]=1)=3. Interval [1,5] = "gbdba": g != a, so max(dp[2][5]=3, dp[1][4]=3)=3.

Finally, for length 6, the full interval [0,5] = "agbdba": s[0]=a, s[5]=a, they match, so dp[0][5] = dp[1][4] + 2 = 3 + 2 = 5. The inner interval [1,4] = "gbdb" had value 3 ("bdb"), and adding the two 'a' characters on both ends yields "abdba" with length 5. This demonstrates how matching outer characters allow us to extend an inner palindrome, while mismatches force us to choose the best sub-interval.

Reconstruction Trace

To reconstruct the actual subsequence, we backtrack from dp[0][5]. Since s[0]==s[5]=='a', we include both 'a's and move to [1,4]. At [1,4], s[1]=g != b=s[4], and dp[2][4]=3 >= dp[1][3]=1, so we move to [2,4]. At [2,4], s[2]==s[4]=='b', include both 'b's and move to [3,3]. At [3,3], we have a single character 'd', which is the center of the palindrome. Collecting left part ['a','b'] plus center 'd' plus reversed right part ['b','a'] gives "abdba".

5. Complexity Analysis

Complexity analysis is essential for choosing the right implementation and understanding scalability. The longest palindromic subsequence has well-defined bounds for each approach, and the trade-offs between time and space are instructive for system design and interview discussions.

The brute force recursive solution has exponential time complexity because it explores all subsequences. There are 2^n subsequences, and checking each for palindrome property is O(n), though the recursive branching analysis yields O(2^n) directly. Its space complexity is O(n) due to recursion stack depth, but it is unusable beyond small n. Memoization and tabulation both achieve O(n^2) time because there are n^2 intervals and each is computed in O(1) time using previously computed results.

Space complexity varies. The full tabulation table requires O(n^2) integers. Memoization also uses O(n^2) for the cache plus O(n) recursion stack. The space-optimized version reduces this to O(n) by noting that computing dp[i][j] only needs the next row (i+1) and the current row's previous column. However, this optimization sacrifices the ability to reconstruct the subsequence, which requires the full table for backtracking.

Best, Average, and Worst Case Nuances

Unlike sorting algorithms, the DP approaches for longest palindromic subsequence have the same asymptotic complexity in all cases because the table size depends only on n, not on the content of the string. Whether the string is all identical characters like "AAAAA" or all distinct like "ABCDE", we still fill n^2 cells. The only variation is in the constant factors and early exits: if characters match often, we take the dp[i+1][j-1]+2 path, otherwise the max path, but both are O(1).

For brute force, the best case is still exponential; there is no early termination that changes the asymptotic bound. In practice, memoization may be faster than tabulation for sparse cases where many intervals are not visited, but for longest palindromic subsequence every interval is eventually needed in the worst case, so both converge to O(n^2).

Scalability Considerations

For n = 1000, O(n^2) means 1,000,000 operations, which is trivial in Python. For n = 5000, it becomes 25,000,000 operations, which may be borderline in Python but feasible in PyPy or with Numba. Memory for O(n^2) with n=5000 requires 25 million integers; at 28 bytes per Python int, that is ~700 MB, which is too large. This is where the O(n) space optimization becomes critical, or switching to an array('H') or numpy for compact storage.

6. Variations and Optimizations

Beyond the standard length computation, several variations of the longest palindromic subsequence problem appear in practice and interviews. Understanding these extensions demonstrates deeper mastery and prepares you for follow-up questions.

One common variation is counting the number of distinct longest palindromic subsequences, not just finding the length. Another is finding the minimum number of insertions or deletions to make a string palindrome, which is directly related: min insertions = n - LPS length, and min deletions = n - LPS length. The minimum insertions problem can be solved with the same DP table, and the reconstruction can output the actual palindrome after insertions.

Another optimization is using bitset or bit-parallel techniques for the LCS reduction. Since LCS can be accelerated with bitset DP to O((n^2)/w) where w is the word size, this can speed up longest palindromic subsequence for large alphabets or binary strings. For strings over small alphabets like DNA (A,C,G,T), Four Russians speedup can also be applied, though it is rarely required in interviews.

Reconstructing All LPS

To enumerate all longest palindromic subsequences, you can perform a DFS over the DP table, branching whenever dp[i+1][j] == dp[i][j-1]. This can produce exponentially many results in the worst case (e.g., "AAAAA" has many distinct LPS of same length but they are identical as strings; for counting distinct strings, deduplication is needed). The enumeration is useful for bioinformatics where multiple optimal alignments are relevant.

Minimum Insertions to Form Palindrome

The DP for minimum insertions is almost identical: let dp[i][j] be minimum insertions to make s[i..j] palindrome. If s[i]==s[j], dp[i][j]=dp[i+1][j-1]; else dp[i][j]= min(dp[i+1][j], dp[i][j-1]) + 1. The answer is dp[0][n-1] = n - LPS length. This variation is often asked as a follow-up and can be solved without extra code by reusing the LPS length.

Handling Large Inputs and Unicode

For very long strings, Python recursion limits and memory become bottlenecks. Iterative tabulation avoids recursion depth issues. For Unicode strings, the algorithm works unchanged because Python strings are sequences of Unicode code points, but be aware that grapheme clusters may require normalization. If the input is a list of words or tokens rather than characters, the same DP applies with equality defined over tokens.

7. Real-World Applications

While the longest palindromic subsequence may seem like an academic exercise, its underlying techniques power numerous real-world systems. Any domain involving sequence comparison, error correction, or structural symmetry can benefit from LPS and its close relatives like LCS and edit distance.

In bioinformatics, DNA and RNA sequences are analyzed for palindromic structures that indicate hairpin loops and secondary structures. Palindromic subsequences in genomes can signal regulatory sites or viral integration points. The LPS algorithm, extended to handle complementary base pairing (A-U, G-C) instead of exact equality, helps predict RNA folding. Sequence alignment tools like BLAST and Needleman-Wunsch use DP tables structurally identical to the LPS table.

In text processing and diff tools, finding the longest palindromic subsequence is a special case of finding the longest common subsequence between a file and its reverse, which is used for detecting mirrored structures or for data compression. Version control systems use LCS to compute diffs, and understanding LPS helps engineers optimize those diff algorithms for specific data patterns.

Web Servers and Databases

In web servers, LPS-related algorithms appear in URL routing and cache key normalization where palindromic or symmetric patterns indicate redundant requests. In databases, fuzzy string matching for deduplication uses edit distance, which shares the same DP foundation. For example, finding near-duplicate product titles can be framed as finding long common subsequences, and the optimizations learned from LPS (space reduction, early termination) directly apply.

Networks and Error Correction

In network coding, palindromic subsequences are used to design reversible codes where data can be read forwards and backwards for error resilience. The ability to compute minimal insertions to achieve palindrome property is used to add check symbols that make transmitted sequences palindromic, allowing receivers to detect errors by checking symmetry. This is conceptually similar to how CRC checks work but at the sequence level.

8. Comparison with Alternatives

Choosing the right approach depends on whether you need just the length, the actual subsequence, or the best performance for large inputs. The longest palindromic subsequence can be solved via several related algorithms, each with different trade-offs in time, space, and implementation complexity. Understanding these alternatives helps you select the appropriate tool and defend your choice in interviews.

The brute force method is only useful as a baseline for correctness testing. Memoization is intuitive for those comfortable with recursion and is easy to derive from the recurrence. Tabulation is generally preferred in production code because it avoids recursion limits and has better cache locality. The LCS reduction is elegant but requires careful handling to avoid O(n^2) extra space for the reversed string, though that is usually negligible.

For the related longest palindromic substring problem, Manacher's algorithm achieves O(n) time, but it does not apply to subsequences because it relies on contiguity. Attempting to use Manacher's for subsequence will give incorrect results. Similarly, greedy approaches fail because locally optimal choices (e.g., always matching the earliest possible pair) do not guarantee global optimality, which is why DP is necessary.

When to Use Which

Use memoization when you need to quickly prototype and the constraints are moderate (n < 1000). Use tabulation when you need to reconstruct the subsequence or when recursion depth is a concern. Use the space-optimized version when n is large and you only need the length, such as in a streaming or memory-constrained environment. Use the LCS reduction when you already have a highly optimized LCS implementation available in your codebase.

Why Greedy Fails

A common misconception is that a greedy strategy like "always match the outermost equal characters" works. Counterexample: s = "abac". Greedy matching outer 'a's gives "aba" length 3, which happens to be optimal here, but for s = "abccaa", greedy might match first 'a' with last 'a' prematurely and miss a longer inner palindrome. DP explores both options—matching or skipping—so it never commits to a locally attractive but globally suboptimal match.

9. Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing longest palindromic subsequence. Recognizing these pitfalls early saves debugging time and prevents wrong answers in interviews and production.

One frequent mistake is confusing substring and subsequence, leading to use of center expansion or incorrect DP dimensions. Another is off-by-one errors in DP table indexing, especially when handling the dp[i+1][j-1] case where i+1 > j-1. For length 2 intervals where i+1 > j-1, the inner interval is empty and should contribute 0, not be accessed out of bounds. Proper base case handling for length 2 is crucial: if s[i]==s[j] and j==i+1, then dp[i][j]=2 directly.

Another pitfall is forgetting to escape or handle empty string input. The DP table for n=0 should return 0, not crash. Similarly, strings with all same characters like "AAAA" should return n, and the reconstruction should produce "AAAA". Testing these edge cases is essential. Also, when reconstructing, ties where dp[i+1][j] == dp[i][j-1] can be resolved arbitrarily, but you must be consistent to avoid infinite loops; typically prefer moving i forward.

Best Practices for Robust Code

Always write a helper to validate inputs and handle n <= 2 separately for clarity. Use descriptive variable names like dp and n, and comment the recurrence. When optimizing space, keep a copy of the previous diagonal value before overwriting, as shown in the space-optimized code. For interview settings, start with the tabulation approach because it is iterative, easy to explain, and allows reconstruction, which interviewers often ask for as a follow-up.

Use Python's sys.setrecursionlimit if you must use recursion for large n, but prefer iterative to avoid recursion overhead. For performance-critical code, consider using array('H') or list of arrays from module 'array' or numpy to reduce memory. Profile with timeit for n=100, 500, 1000 to demonstrate scalability. Finally, always test with at least five cases: empty string, single character, all same, no palindrome longer than 1, and a known example like "BBABCBCAB".

Debugging Tips

Print the DP table for small strings to visually verify the filling order. For s="agbdba", the table should be symmetric and the diagonal all 1s. If your table shows incorrect values, check the loop order: i must go from n-1 down to 0, or length must increase from 2 to n. Reversing the order will use uncomputed values. Use assertions like assert dp[i][j] >= dp[i+1][j] and dp[i][j] >= dp[i][j-1] to catch logic errors early.

10. Interview Questions

Interviewers love the longest palindromic subsequence because it tests recursion, DP, and reconstruction in one problem. Below are common questions with high-level solution strategies to help you prepare.

Question 1: Compute the Length of the Longest Palindromic Subsequence

Prompt: Given a string s, return the length of its longest palindromic subsequence. Example: s="bbbab" returns 4 ("bbbb"). This is the standard problem. Expected solution is O(n^2) DP with tabulation or memoization. Be ready to explain the recurrence and fill order, and to analyze time and space. Follow-up: Can you do it in O(n) space? Answer: Yes, with two rows or one row plus diagonal variable if only length is needed.

Question 2: Return the Actual Longest Palindromic Subsequence

Prompt: Instead of just the length, return one longest palindromic subsequence string. Example: s="cbbd" could return "bb". Solution: Build the full O(n^2) DP table, then backtrack from (0, n-1) as shown in the tabulation code. At each step, if s[i]==s[j], include both characters and move diagonally; otherwise move in the direction of the larger DP value. Complexity remains O(n^2) time and O(n^2) space for reconstruction. Be careful to handle the center character when i==j.

Question 3: Minimum Insertions to Make a String Palindrome

Prompt: Find the minimum number of insertions needed to make s a palindrome. You may insert characters anywhere. Example: s="ab" needs 1 insertion ("aba" or "bab"), s="mbadm" needs 2. Solution: Answer is n - LPS length. Alternatively, compute DP where dp[i][j] = min insertions for s[i..j]. Recurrence: if s[i]==s[j], dp[i][j]=dp[i+1][j-1]; else dp[i][j]= min(dp[i+1][j], dp[i][j-1]) +1. This tests whether you understand the relationship between LPS and edit operations.

Question 4: Minimum Deletions to Make a String Palindrome

Prompt: What is the minimum number of deletions to make s palindrome? Example: s="abca" needs 1 deletion ("aba" or "aca"). Solution: Identical to insertions: n - LPS length. Some interviewers ask for the actual deletions or the resulting palindrome, which again requires reconstruction. A common twist is to ask for minimum deletions to make the string palindrome where you can only delete, not insert, which is the same DP.

Question 5: Longest Palindromic Subsequence vs. Longest Palindromic Substring

Prompt: Explain the difference and solve both. How would your approach change? Solution: For subsequence, use O(n^2) interval DP as described. For substring, use O(n^2) center expansion or O(n) Manacher's algorithm because contiguity allows linear time. Discuss why Manacher's cannot be adapted to subsequence and why DP is necessary for subsequence. This question tests conceptual clarity and ability to contrast related problems without confusing them.

Preparation tip: Practice coding all variations on a whiteboard without IDE assistance, and be ready to walk through a 5-6 character example step by step. Interviewers often ask you to dry-run your code on "agbdba" or "bbbab" to verify you understand the table filling and backtracking logic.