String DP

Classic sequence DP established the shape: state is a pair of prefixes, and a match reads the diagonal while a mismatch takes the better neighbour. This page is the same table with two substitutions applied, and each one produces a problem that looks unrelated.

Swap max for + and “longest common subsequence” becomes “how many subsequences” — LC 115. Let the pattern contain ?, * or . and the mismatch branch splits on the pattern character instead of the text — LC 44 and LC 10.

The payoff is that you do not memorise three recurrences. You memorise one table and two substitutions, and you can derive a problem you have not seen at the whiteboard, which is what these questions are actually testing.

What you’ll learn

• Why max → + converts an optimisation into a count, and what happens to the base case when it does.
• The two meanings of * — one in wildcards, a different one in regex — and why conflating them is the usual source of wrong answers.
• The asymmetric base row that regex needs and wildcards do not.
• How to derive LC 10 from LC 44 rather than learning both.

The cue

You are looking at string DP when…

• Two strings and a question about aligning, matching or transforming one into the other, where the answer depends on both prefixes.
• Or one string and one pattern containing wildcards, so a single pattern character can consume a variable number of text characters.
• The answer is a count of ways rather than a best value — that is the + variant.

The state is always the same: dp[i][j] answers the question for a[:i] and b[:j]. What varies is only the combine step.

Question	Combine
longest / shortest	max or min
how many ways	+
does it match at all	or

Reach for something else when only one string is involved (that is prefix DP), when the required match is contiguous (that is a sliding window or KMP, both faster), or when a greedy two-pointer scan suffices — LC 392 “is subsequence” is $O(n)$ greedy and needs no table at all.

Visual intuition

Start from the table you already know. Every problem on this page is this grid with the combine step changed:

dpThe same grid — only the operator changesLCS as the base case of the family

rows: a = "rabbbit"cols: b = "rabbit"

1def lcs(a, b):2    m, n = len(a), len(b)3    dp = [[0] * (n + 1) for _ in range(m + 1)]4    for i in range(1, m + 1):5        for j in range(1, n + 1):6            if a[i - 1] == b[j - 1]:7                dp[i][j] = dp[i - 1][j - 1] + 1     # diagonal + 18            else:9                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])10    return dp[m][n]

base caseRow 0 and column 0 are all zeros: the longest common subsequence with an empty string is empty. Those sentinels are why the loops can start at 1 and never test for out-of-range indices.

Play‹›1/86⟲

With max, this counts the longest common subsequence. Replace max with + and it counts HOW MANY ways the second string appears as a subsequence of the first — which is LC 115, and the answer for these two strings is 3. The dependency arrows are identical; only what happens at the cell differs.

From max to plus: Distinct Subsequences

LC 115: how many distinct subsequences of s equal t?

distinct_subsequences.py

def num_distinct(s, t):                       # LC 115
    m, n = len(s), len(t)
    # dp[i][j] = ways that t[:j] appears as a subsequence of s[:i]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
 
    # Base: the EMPTY target is matched exactly one way -- by taking nothing.
    for i in range(m + 1):
        dp[i][0] = 1
 
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # Always available: skip s[i-1] entirely.
            dp[i][j] = dp[i - 1][j]
            if s[i - 1] == t[j - 1]:
                # Additionally: USE s[i-1] to match t[j-1].
                dp[i][j] += dp[i - 1][j - 1]
    return dp[m][n]
 
 
print(num_distinct("rabbbit", "rabbit"))      # expect 3
print(num_distinct("babgbag", "bag"))         # expect 5

Compare that with LCS. The structure is identical; three things differ:

	LCS	Distinct Subsequences
base row dp[i][0]	0	1
on a match	dp[i-1][j-1] + 1	dp[i-1][j] + dp[i-1][j-1]
on a mismatch	max(dp[i-1][j], dp[i][j-1])	dp[i-1][j]

The base case flip is not cosmetic — it is the whole answer

For a counting problem the empty target is matched exactly one way: by choosing nothing. So dp[i][0] = 1, not 0.

Leave it at 0 and every cell multiplies through zero — the function returns 0 for every input, which at least fails loudly. The subtler error is setting dp[0][j] = 1 as well; a non-empty target cannot be matched by an empty source, so that row must stay 0.

And note the mismatch branch reads only dp[i-1][j], not both neighbours. Taking max or a sum of both would double-count: dp[i][j-1] is a different question, not an alternative path to this one.

Dry run

s = "rabbbit", t = "rabbit". The interesting column is j = 4 (t[:4] = "rabb"), where the three bs in s create the three distinct matches.

i	s[i-1]	dp[i][3] ("rab")	dp[i][4] ("rabb")	why
3	b	1	0	"rab" matched once; "rabb" needs a second b
4	b	1	1	match: dp[3][4] + dp[3][3] = 0 + 1
5	b	1	2	match: dp[4][4] + dp[4][3] = 1 + 1
6	i	1	2	no match, so carry dp[5][4]
7	t	1	2	carry

Each additional b in s adds one more way to match the second b of t, accumulating 0 → 1 → 2. Continuing to dp[7][6] gives 3, the three choices of which b to skip.

Read the accumulation again: the count grows because dp[i-1][j] carries every way found so far while dp[i-1][j-1] adds the new ones. That is the + doing what max cannot.

Wildcards: two different meanings of *

This is where most confusion lives. * means something different in the two problems, and the recurrences differ accordingly.

	LC 44 Wildcard	LC 10 Regex
? / .	matches exactly one character	matches exactly one character
*	matches any sequence, including empty — stands alone	applies to the preceding character, meaning zero or more of it
"a*" matches	"a", "ab", "axyz" — anything starting with a	"", "a", "aa", "aaa" — only as

wildcard_and_regex.py

def is_match_wildcard(s, p):                   # LC 44:  ?  and standalone *
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    # A leading run of '*' can match the empty string.
    for j in range(1, n + 1):
        if p[j - 1] == "*":
            dp[0][j] = dp[0][j - 1]
 
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                # skip the '*'  OR  let it consume s[i-1]
                dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
            elif p[j - 1] == "?" or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]
 
 
def is_match_regex(s, p):                      # LC 10:  .  and  x*
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    # 'x*' pairs can vanish, so they may match the empty string.
    for j in range(2, n + 1):
        if p[j - 1] == "*":
            dp[0][j] = dp[0][j - 2]
 
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                prev = p[j - 2]
                # zero occurrences: drop the 'x*' pair entirely
                dp[i][j] = dp[i][j - 2]
                # one or more: 'x' must match s[i-1], then reuse the same 'x*'
                if prev == "." or prev == s[i - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
            elif p[j - 1] == "." or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]
 
 
print([is_match_wildcard("adceb", "*a*b"), is_match_wildcard("cb", "?a")])
# expect [True, False]
print([is_match_regex("aab", "c*a*b"), is_match_regex("mississippi", "mis*is*p*.")])
# expect [True, False]

The two * branches say it precisely:

• Wildcard: dp[i][j-1] (the * matches nothing) or dp[i-1][j] (the * swallows one more character and remains available).
• Regex: dp[i][j-2] (drop the whole x* pair) or, if x matches the current character, dp[i-1][j] (consume it and keep the pair for more).

The j-2 is the difference. Regex * is bound to the character before it, so skipping it means skipping two pattern positions.

The base row is where regex diverges most

Wildcard: a leading run of * matches the empty string, so dp[0][j] = dp[0][j-1] whenever p[j-1] == '*'.

Regex: only a complete x* pair can vanish, so the loop starts at j = 2 and reads dp[0][j-2]. This is why p = "a*b*c*" matches "" but p = "*" alone is not even a valid regex pattern in LC 10.

Complexity

Problem	Time	Space	Space-optimised
LC 115 Distinct Subsequences	$O(mn)$	$O(mn)$	$O(n)$ — one row
LC 44 Wildcard Matching	$O(mn)$	$O(mn)$	$O(n)$
LC 10 Regular Expression Matching	$O(mn)$	$O(mn)$	$O(n)$
LC 97 Interleaving String	$O(mn)$	$O(mn)$	$O(n)$

All $O(mn)$, and all reduce to one row because each row reads only the row above plus already-written cells in the current row. Offer the table first and the space optimisation as a follow-up — the one-row version is easy to get subtly wrong under pressure, and volunteering it prematurely invites a bug.

For LC 115 mention the overflow caveat: counts grow combinatorially. Python is fine; in Java or C++ the answer can exceed a 64-bit integer and the problem usually promises it fits.

The variant map

Problem	Combine	The distinguishing detail
1143 LCS	max	the base of the family
115 Distinct Subsequences	+	dp[i][0] = 1; mismatch reads only dp[i-1][j]
44 Wildcard	or	* is standalone; skip one pattern position
10 Regex	or	* binds to the previous char; skip two positions
97 Interleaving String	or	dp[i][j] = can a[:i] and b[:j] interleave to c[:i+j]
72 Edit Distance	min	base row counts up, not zeros
392 Is Subsequence	—	not DP — greedy two pointers, $O(n)$

LC 392 is the trap in this family

“Is t a subsequence of s” needs no table: walk both strings with two pointers and advance the t pointer on every match. $O(n)$ time, $O(1)$ space.

Reaching for a DP table there is a real signal problem — it says you pattern-matched on “two strings” without asking whether the simpler tool works. The follow-up does justify DP: “now answer it for 10⁴ different t values against one s”, where preprocessing s pays off.

Pitfalls

• dp[i][0] = 0 in a counting problem. The empty target is matched one way. Every cell then multiplies through zero.
• Setting dp[0][j] = 1 too. A non-empty target cannot be matched by an empty source; that row stays 0.
• Taking both neighbours on a mismatch in LC 115. Only dp[i-1][j] is a path to this cell. Including dp[i][j-1] double-counts.
• Using j-1 instead of j-2 for regex *. The * binds to the character before it, so the pair skips two positions together.
• Forgetting the regex base row. Without dp[0][j] = dp[0][j-2], patterns like "a*b*" fail to match "".
• Reaching for DP on LC 392. Two pointers, $O(n)$. Check whether greedy works before building a table.
• Optimising space before the table is correct. Get $O(mn)$ right, state that one row suffices, then reduce only if asked.

Interview follow-ups

They ask	What they’re checking	The answer
“Turn LCS into a counting problem”	Whether you see the family	Replace max with +, flip the base row to 1, and drop dp[i][j-1] from the mismatch branch. Same table
“Why is dp[i][0] = 1 and not 0?”	Base-case reasoning	The empty target is matched exactly one way — by choosing nothing. With 0 every product is 0
“Difference between wildcard * and regex *?”	Precision	Wildcard * is standalone and matches any sequence. Regex * binds to the preceding character and means zero or more of that char — so skipping it skips two pattern positions
“Derive LC 10 from LC 44”	Whether you learned one thing or two	Same skeleton; change the * branch to look at p[j-2] and skip two positions, and change the base row to dp[0][j-2]
“Reduce the space”	Optimisation	Each row reads only the row above and cells already written in this row, so one row of length n+1 suffices. Iterate carefully — the in-place update order matters
“Is t a subsequence of s?”	Whether you over-apply DP	Two pointers, $O(n)$, no table. DP only becomes right when many t are queried against one s
“The count overflows”	Language awareness	Python’s ints are unbounded. In Java or C++ use long and note that the problem usually guarantees the answer fits

Practice

5 problems

1 easy1 medium3 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○392Is SubsequenceeasyLeetCode Top Interview 150
• ○97Interleaving StringmediumNeetCode 150LeetCode Top Interview 150
• ○10Regular Expression MatchinghardNeetCode 150
• ○44Wildcard Matchinghard
• ○115Distinct SubsequenceshardNeetCode 150

Exercises

LC 115 — Distinct Subsequences · Hard

pch.exerciseTag pch.exerciseTitle

LC 44 — Wildcard Matching · Hard

pch.exerciseTag pch.exerciseTitle

LC 10 — Regular Expression Matching · Hard

pch.exerciseTag pch.exerciseTitle

Self-check

pch.quizTag String DP — self-check

1. To turn LCS into Distinct Subsequences, what changes?

   A Nothing — they are the same problem B Replace max with +, set dp[i][0] = 1 instead of 0, and read only dp[i-1][j] on a mismatch C Reverse one of the strings first D Add a third dimension
   pch.quizShowAnswer

   B — Replace max with +, set dp[i][0] = 1 instead of 0, and read only dp[i-1][j] on a mismatch — One operator, one base case, one dropped term. The table shape and dependency arrows are identical — which is why learning the family beats memorising the members.

2. Why is dp[i][0] = 1 in a counting problem?

   A To avoid a division by zero B Because the empty target is matched exactly one way — by choosing nothing C Because indices start at 1 D It should be 0
   pch.quizShowAnswer

   B — Because the empty target is matched exactly one way — by choosing nothing — With 0 every cell multiplies through zero and the function returns 0 for all inputs. Note dp[0][j] must stay 0 though: a non-empty target cannot be matched by an empty source.

3. On a MISMATCH in LC 115, why read only dp[i-1][j] and not both neighbours?

   A For efficiency B Because dp[i][j-1] answers a different question, not an alternative path to this cell — including it double-counts C Because the strings have different lengths D Both should be read
   pch.quizShowAnswer

   B — Because dp[i][j-1] answers a different question, not an alternative path to this cell — including it double-counts — In LCS both neighbours are alternative alignments and max picks the better. In a count they are not alternatives — the only way to reach dp[i][j] without using s[i-1] is dp[i-1][j].

4. What is the difference between wildcard `*` (LC 44) and regex `*` (LC 10)?

   A None — both match any sequence B Wildcard `*` stands alone and matches any sequence; regex `*` binds to the preceding character and means zero or more of THAT char — so skipping it skips two pattern positions C Regex `*` matches exactly one character D Wildcard `*` cannot match the empty string
   pch.quizShowAnswer

   B — Wildcard `*` stands alone and matches any sequence; regex `*` binds to the preceding character and means zero or more of THAT char — so skipping it skips two pattern positions — This is the single most common source of wrong answers in this family. 'a*' matches 'axyz' as a wildcard and only strings of a's as a regex, and the j-2 in the recurrence follows directly.

5. 'Is t a subsequence of s?' (LC 392) — what is the right approach?

   A A 2-D DP table, like the rest of this family B Two pointers, O(n) time and O(1) space — no table needed C Sort both strings first D A rolling hash
   pch.quizShowAnswer

   B — Two pointers, O(n) time and O(1) space — no table needed — The trap of this page. Reaching for DP here signals pattern-matching on 'two strings' without checking whether greedy works. DP only becomes right when many t values are queried against one s.

Recall card

• State is always the same — dp[i][j] for a[:i] and b[:j]. Only the combine step varies: max/min for optimisation, + for counting, or for matching.
• Counting base case — dp[i][0] = 1 (empty target, one way), dp[0][j] = 0.
• Counting mismatch — read only dp[i-1][j]. Both neighbours double-counts.
• Wildcard * — standalone. dp[i][j-1] or dp[i-1][j].
• Regex * — binds to p[j-2]. dp[i][j-2], or dp[i-1][j] when p[j-2] matches. Base row from j = 2.
• Complexity — $O(mn)$ time, reducible to $O(n)$ space. Get the table right first.
• LC 392 is not DP — two pointers, $O(n)$.

Recap

• All of this family is one table with a different operator at the cell. Learn the substitutions, not the problems.
• max → + converts optimisation into counting, and the base row must flip to 1 or the whole table collapses to zero.
• Wildcard and regex * mean different things; the j-2 in the regex recurrence is that difference made concrete.
• Check whether greedy works before building a table — LC 392 is $O(n)$ with two pointers and appears in this family only as a trap.

Next: Bitmask and Tree DP — when the state is a set rather than an index.