LCS and Edit Distance
You know LIS with 1D states. Now work with two sequences simultaneously. LCS and Edit Distance are the basis of all string comparison algorithms.
Lessons
1. Intro
The Goal
2. Two-Dimensional State
Two sequences
3. LeetCode 1143 Longest Common Subsequence - Problem Statement
LeetCode 1143
4. LeetCode 1143 Longest Common Subsequence - State Design
The 2D table
5. LeetCode 1143 Longest Common Subsequence - Transition
Match or skip
6. LeetCode 1143 Longest Common Subsequence - Implementation
The code
7. LeetCode 1143 Longest Common Subsequence - Walkthrough
Tracing the algorithm
8. Quiz: LCS Concepts
Knowledge check
9. LeetCode 1143 Longest Common Subsequence - Reconstruction
Finding the actual sequence
10. Lessons from LCS
summary
11. Challenge: LCS Space Optimization
Reducing memory
12. LeetCode 712 Minimum ASCII Delete Sum for Two Strings - Problem Statement
LeetCode 712
13. LeetCode 712 Minimum ASCII Delete Sum for Two Strings - Weighted DP
Cost instead of count
14. LeetCode 712 Minimum ASCII Delete Sum for Two Strings - Implementation
The code
15. LeetCode 712 Minimum ASCII Delete Sum for Two Strings - Walkthrough
Weighted LCS variant
16. LeetCode 72 Edit Distance - Problem Statement
LeetCode 72
17. LeetCode 72 Edit Distance - Operations
Three choices
18. LeetCode 72 Edit Distance - State Design
Minimum cost
19. LeetCode 72 Edit Distance - Transition
The recurrence
20. LeetCode 72 Edit Distance - Implementation
The code
21. LeetCode 72 Edit Distance - Walkthrough
Tracing transformations
22. Challenge: Edit Distance Reconstruction
Finding the operations
23. Quiz: Edit Distance
Knowledge check
24. Lessons from Edit Distance
summary
25. Pattern - String DP
Recognition tips
26. LeetCode 516 Longest Palindromic Subsequence - Problem Statement
LeetCode 516
27. LeetCode 516 Longest Palindromic Subsequence - Walkthrough
LCS with itself
28. LeetCode 583 Delete Operation for Two Strings - Problem Statement
LeetCode 583
29. LeetCode 115 Distinct Subsequences - Problem Statement
LeetCode 115
30. LeetCode 115 Distinct Subsequences - Walkthrough
Counting occurrences
31. Quiz: String DP Patterns
Knowledge check
32. LeetCode 1092 Shortest Common Supersequence - Problem Statement
LeetCode 1092
33. LeetCode 1092 Shortest Common Supersequence - The LCS Connection
Length formula
34. LeetCode 1092 Shortest Common Supersequence - Implementation
The code
35. LeetCode 1092 Shortest Common Supersequence - Walkthrough
Building from LCS
36. LeetCode 44 Wildcard Matching - Problem Statement
LeetCode 44
37. LeetCode 44 Wildcard Matching - State Design
Boolean 2D DP
38. LeetCode 44 Wildcard Matching - Implementation
The code
39. LeetCode 44 Wildcard Matching - Walkthrough
Pattern matching DP
40. What's Next
Preview of Interval DP
41. Section Recap
What we learned
Practice Problems
The canonical LCS problem - master this first.
Classic Levenshtein distance with insert/delete/replace operations.
Requires reconstructing the actual LCS string, not just its length.
LCS of string with its reverse - elegant problem transformation.
Counts ways to form subsequence - extends LCS to combinatorics.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Modified LCS scoring. Teaches adapting classic DP to new objective functions.
Edit distance with operation reconstruction. Must output the actual edit sequence.
Transform sequences with weighted operations. Generalized edit distance with costs.
Check if s3 interleaves s1 and s2. 2D DP tracking positions in both strings.
Pattern matching with . and *. The hardest string matching DP - interview classic.
Minimum operations to make array uniform. Interval DP on strings.
Check if string can be formed from two disjoint subsequences. DP on two pointers.
Construct grid with string constraints. Pattern-based construction.
Count paths on tetrahedron. Matrix DP with state transitions.
Assign values satisfying comparison constraints. Graph + DP approach.
Check if 3 strings are disjoint subsequences. 3D DP with online updates.
Maximize profit with weapon/armor constraints. Segment tree + DP.
Count quadruples with equal endpoints. Prefix counting + DP.