LESSON 30 · PATTERN GUIDE

String DP / Sequence DP

Use a table of prefix states to compare sequences, edit strings, or count subsequence relationships.

FIRST, LEARN THE PATTERNdp[i][j] usually summarizes the best result using prefixes of lengths i and j; transitions compare the last characters or skip one side.

The task asks for longest common subsequence, edit distance, matching subsequences, or minimum edits between strings.

How to approach it

Define what the two prefix lengths mean, initialize empty-prefix rows, and derive transitions for matching and nonmatching characters.

Watch out for

Index offsets are a common source of bugs. Distinguish subsequence (can skip) from substring (must be contiguous).

A CLOSER EXPLANATION

A two-dimensional DP compares prefixes of two sequences. If the current characters match, extend a result from both shorter prefixes; otherwise, skip one character from either sequence and keep the better result. Empty-prefix rows define what happens when one sequence has no characters.

NOW YOU TRY

Practice question

What is the longest common subsequence length of 'stone' and 'long'?

EXAMPLEa = 'stone', b = 'long'Give your answer before revealing the explanation.

Show a hint

Compare prefixes; when characters match extend the diagonal state, otherwise take the better skip.

Show an answer

2 ('on').

CONNECT IT TO REAL LIFE

String DP / Sequence DP at work

A document editor compares old text 'plan' with new text 'plant'. What is the longest sequence of characters that stays in order in both versions?

Show one possible approach

'plan', length 4. The longest common subsequence preserves character order while allowing extra characters in either version to be skipped.

Practice next

Use these problem IDs to find additional practice for this pattern:

114372115583971312