How does your spell checker suggest corrections? How does git diff align old and new files? These problems compare two strings character by character, finding optimal alignments or transformations.
String DP tracks position in one or more strings. Your state is usually : the answer for the first characters of string A and first of string B. I'll show you alignment problems, palindrome partitioning, pattern matching, and counting distinct subsequences.
