Subsequence vs. Substring: DP & Two-Pointer Patterns

Welcome to the final lesson of our module on advanced dynamic programming. In our last session, you mastered the "expand around center" technique for finding the longest palindromic substring. This was a great example of a two-pointer approach applied to a problem about contiguous character sequences.

This lesson serves as a capstone, bringing together everything we've covered on string manipulation. Our goal is to synthesize your knowledge of dynamic programming (from problems like LCS and LIS) and pointer-based techniques into a coherent framework. By the end of this lesson, you will be able to confidently distinguish between subsequence and substring problems and select the most appropriate and efficient algorithm, a critical skill for any coding interview.

1. The Core Distinction: Contiguous vs. Non-Contiguous

The most crucial step in tackling any string problem is to understand the fundamental difference between a substring and a subsequence. A single word can completely change the required approach from a linear-time scan to a quadratic-time dynamic programming solution.

• A substring must be a contiguous block of characters from the original string. Think of it as a "sub-array" of characters.
• A subsequence is formed by deleting zero or more characters from the original string. The remaining characters must maintain their original relative order but are not required to be contiguous.

The following short video provides an excellent, clear breakdown of these terms, along with the related concepts of "subarray" and "subset".

To reinforce this, consider these visual examples:

2. Algorithmic Patterns for Subsequence Problems

Problems involving subsequences often ask for an optimal value (e.g., longest, shortest, number of) that depends on a series of choices: for each character, do we include it in our subsequence or not? This structure of "optimal substructure" and "overlapping subproblems" makes them a natural fit for Dynamic Programming.

The Default Choice: Dynamic Programming

As you saw with Longest Common Subsequence (LCS) and Longest Increasing Subsequence (LIS), the standard approach is to build a DP table. A state like dp[i][j] typically represents the solution considering prefixes of the input string(s). The recurrence relation then defines how to transition from smaller subproblems to larger ones.

For instance, the Longest Palindromic Subsequence (LPS) problem is elegantly solved by finding the LCS of the string and its reverse. This works because a palindrome is a sequence that is identical to its reverse, so the longest such sequence is precisely the longest common subsequence between the original string and its reversed version.

The Special Case: Greedy Two-Pointers

While DP is the general tool, there's a crucial, efficient exception. For the simpler problem of checking if string s is a subsequence of string t, a greedy two-pointer approach is far more efficient.

The following article section discusses this exact scenario, contrasting the DP solution with the much faster greedy one.

To see this greedy algorithm in action, the following video provides a clear walkthrough.

3. Algorithmic Patterns for Substring Problems

Because substrings must be contiguous, we can often solve problems using methods that "scan" through the string, which are typically more efficient than $O(N^2)$ DP.

The Go-To Tools: Sliding Window and Two Pointers

You have already encountered these patterns multiple times.

• Sliding Window: Ideal for problems asking for the longest, shortest, or a count of substrings that satisfy a certain property (e.g., "Longest Substring with K Distinct Characters"). You maintain a "window" and expand/shrink it as you iterate through the string.
• Two Pointers: A versatile technique. The "expand around center" method for Longest Palindromic Substring is a perfect example that leverages the contiguous and symmetric nature of palindromic substrings.

The Occasional Tool: Dynamic Programming

While less common, DP can be used for substring problems. However, the recurrence must be adapted to enforce contiguity. A classic example is the "Longest Common Substring" problem.

Let's see how its DP formulation differs from that of LCS.

This else -> 0 trick is the key takeaway for how DP can enforce contiguity. It makes the state dp[i][j] represent the length of the common substring ending at s1[i-1] and s2[j-1].

4. A Decision-Making Framework

To summarize, here is a practical framework to help you choose the right pattern during an interview.

Conclusion and Course Wrap-Up

In this final lesson, we've established a clear mental model for dissecting string problems. The distinction between a contiguous substring and a non-contiguous subsequence is your first and most important clue. Substrings often point toward efficient linear-scan techniques like sliding windows, while subsequences typically call for the powerful, choice-based logic of dynamic programming.

Key Takeaways:

• Substrings are contiguous, lending themselves to Sliding Window and Two-Pointer patterns.
• Subsequences are not contiguous, making Dynamic Programming the general-purpose tool to handle choices.
• A key exception is checking for subsequence existence, where a Greedy Two-Pointer approach is optimal.
• DP can be used for substring problems, but the recurrence must enforce contiguity, often by resetting the count on a mismatch.

With this lesson, you have completed the course. You began with fundamental array techniques like prefix sums and have progressed through linked lists, trees, heaps, backtracking, graphs, and finally, a deep dive into dynamic programming. More important than solving any single problem, you have built a formidable toolkit of algorithmic patterns and, crucially, a methodology for recognizing when to apply them.

Congratulations on your dedication and hard work. The next step is to continue practicing. Use this framework as you tackle new problems on platforms like LeetCode. The more you apply these patterns, the more they will become second nature. Well done