hardDynamic Programming 2DAI-applied~35 min
Prompt Template Edit Distance
An LLM team versions prompt templates and shows a diff to reviewers. The diff renderer needs the minimum number of single-token edits — insert, delete, or substitute — to turn the old template into the new one. (Tokens, not characters, but algorithmically identical to classical edit distance.)
Problem
Given two arrays of tokens a and b, return the minimum number of edits (insert, delete, substitute — each cost 1) to transform a into b.
Input
Two arrays a and b of token strings, each of length 0..500. Tokens are arbitrary strings ≤ 32 chars.
Output
A single integer — the edit distance.
Constraints
- 0 ≤ |a|, |b| ≤ 500
- Each edit costs 1
- Tokens compared by exact equality
Examples
Example 1
Input
a = ["you", "are", "a", "helpful"], b = ["you", "are", "an", "AI", "helpful"]
Output
2
Substitute 'a' → 'an' (1 edit), then insert 'AI' (1 edit). Total 2.
Example 2
Input
a = [], b = ["hello"]
Output
1
One insert.