Subsequence Pattern Matching

Counting how many times a pattern occurs as a subsequence of a string works by deciding, for each character of the string, whether to "use" it toward matching the current pattern character or skip it — and summing the counts of both choices, because a subsequence can pick any subset of positions in order without requiring contiguity.

Recognize the pattern

• Prompt says "subsequence" (not substring) — order matters, contiguity does not.
• Asked to count occurrences (or check existence) of one sequence inside another, character by character.
• Two input sequences of different roles: a longer source string and a shorter pattern to be matched against it.
• Naive recursive idea has an obvious branch: "match this char, or don't" — a signal of overlapping subproblems ripe for memoization.

Brute force → optimal

Brute force: recursively try every way of choosing positions in the string for each pattern character, backtracking. This regenerates the same (string-index, pattern-index) states exponentially many times — O(2^n) time, since each of the n string characters can independently be included or skipped along failed paths.

Optimal (DP): notice the recursion only ever depends on (i, j) — current index into the string and current index into the pattern. Cache it. This collapses the exponential tree into O(n*m) distinct states, each computed in O(1) from smaller ones.

Recurrence

Let dp[i][j] = number of ways to form pattern[0..j) as a subsequence of str[0..i).

dp[0][0] = 1                         // empty pattern matches empty prefix once
dp[i][0] = 1  for all i              // empty pattern always matches (skip everything)
dp[0][j] = 0  for j > 0              // non-empty pattern can't match empty string

if str[i-1] == pattern[j-1]:
    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]   // match this char, OR skip it
else:
    dp[i][j] = dp[i-1][j]                  // must skip, char can't contribute

Answer = dp[n][m].

Complexity, derived

Time: the table has (n+1)*(m+1) cells; each cell does O(1) work (one comparison, one or two additions) → O(n*m).

Space: the full table is O(n*m), but row i only reads row i-1 — rolling to two 1-D arrays of size m+1 gives O(m) space.

Worked example

string = "baxmx", pattern = "ax", expected count = 2.

Row i=3: str[2]='x' matches pattern[1]='x' → dp[3][2]=dp[2][1]+dp[2][2]=1+0=1. Row i=5: str[4]='x' matches again → dp[5][2]=dp[4][1]+dp[4][2]=1+1=2. Matches the two ways: {baxmx} and {baxmx}.

Java

public int countSubsequences(String str, String pattern) {
    int n = str.length(), m = pattern.length();
    long[] prev = new long[m + 1];
    long[] curr = new long[m + 1];
    prev[0] = 1; // empty pattern matches empty prefix

    for (int i = 1; i <= n; i++) {
        curr[0] = 1; // empty pattern always matches any prefix
        for (int j = 1; j <= m; j++) {
            curr[j] = prev[j]; // always allowed to skip str[i-1]
            if (str.charAt(i - 1) == pattern.charAt(j - 1)) {
                curr[j] += prev[j - 1];
            }
        }
        long[] tmp = prev; prev = curr; curr = tmp;
    }
    return (int) prev[m];
}

Pitfalls

• Off-by-one on empty pattern/string: forgetting dp[i][0] = 1 undercounts every row.
• Double counting vs. correct branching: when characters match you must add both "use it" and "skip it" counts, not just one — otherwise you miss matches that reuse a later occurrence of the same character.
• Integer overflow: counts grow combinatorially (e.g. many repeated characters); use long, not int, for large inputs.
• Confusing with distinct subsequences of a single string (LeetCode 940) or with edit-distance style problems — the recurrence looks similar but the semantics differ.

When to use / when not

Use this DP when you need to count or detect subsequence occurrences and inputs are large enough that brute-force recursion (exponential) is infeasible — typical string lengths in the hundreds to thousands.

vs. two-pointer greedy existence check: if you only need a yes/no "is pattern a subsequence of string" (not a count), a single greedy left-to-right two-pointer scan solves it in O(n) time and O(1) space — far cheaper than DP. Reach for DP only when you need a count (or need to reconstruct all matches), not mere existence.

vs. LCS-based approaches: Longest Common Subsequence answers a different question (longest shared subsequence between two strings, not exact pattern coverage count); don't reach for LCS when the question is really about counting exact pattern occurrences.

Takeaways

• The core move is a two-way branch — match-and-advance-both vs. skip-in-string — memoized over (i, j).
• Complexity drops from exponential brute force to O(n*m) time via memoization, and to O(m) space via row rolling.
• Counting needs DP; mere existence needs only a greedy two-pointer scan — don't over-engineer.

Recall: Why must dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (sum, not max or single term) when characters match?

Synthesized from classic subsequence-counting DP (cf. LeetCode 115 Distinct Subsequences) and standard interview-prep pattern catalogs.