Command Palette

Search for a command to run...

Hectal

Module 31

DP on Strings and Sequences

Subsequences and alignments: LIS in O(n log n), LCS and edit distance tables, palindromic DP, counting subsequences, interleaving and wildcard matching.

Advanced 3 lessons 9 problems ~45 min of lessons
Longest Increasing SubsequenceDP on Two Strings

String and sequence DP compares prefixes. For one sequence, the state is usually "best answer ending at index i" (longest increasing subsequence). For two sequences, it's a table indexed by "first i characters of one, first j of the other", and each cell looks at its left, upper and diagonal neighbours.

This module covers the longest increasing subsequence (including the patience-sorting speed-up), longest common subsequence, edit distance, palindromic subsequences and substrings, counting distinct subsequences, interleaving strings, and pattern matching with wildcards.

Best after: DP on Grids

Part 1

Learn the ideas

  1. 31.1Longest Increasing SubsequenceO(n²): dp[i] = 1 + max dp[j] over j < i with a smaller value. O(n log n): keep the smallest possible tail for each length and binary search where each new value goes.16 min
  2. 31.2Two Sequences: LCS and Edit Distancedp[i][j] compares the first i characters of A with the first j of B. Matching characters extend the diagonal; otherwise take the best of dropping one character from either side.16 min
  3. 31.3Palindromic DP and Pattern MatchingPalindromes use an interval state dp[i][j] over one string. Matching problems (interleaving, wildcards, counting subsequences) are two-sequence tables with their own rules.12 min

Part 2

Solve the problems

In order of difficulty. Each one shows the pattern it teaches.

  1. 31.1Longest Increasing SubsequenceMediumLongest Increasing Subsequence

    The quadratic DP, then the tails array with binary search.

  2. 31.2Russian Doll EnvelopesHardLongest Increasing Subsequence

    Turn a 2D chain into 1D LIS by sorting width ascending and height descending.

  3. 31.3Longest Common SubsequenceMediumDP on Two Strings

    The two-sequence table: diagonal on a match, best neighbour otherwise.

  4. 31.4Edit DistanceMediumDP on Two Strings

    Three operations, three neighbours: replace (diagonal), delete (up), insert (left).

  5. 31.5Longest Palindromic SubsequenceMediumInterval DP

    Interval DP on one string: peel matching ends.

  6. 31.6Palindromic SubstringsMediumExpand Around Center

    Counting palindromes: expand from 2n − 1 centres, or a boolean interval table.

  7. 31.7Distinct SubsequencesHardDP on Two Strings

    Counting alignments: on a match, either use the character or skip it.

  8. 31.8Interleaving StringMediumDP on Two Strings

    A boolean grid over two strings; the third string's position is implied by i + j.

  9. 31.9Wildcard MatchingHardDP on Two Strings

    A star matches empty (move in the pattern) or one more character (move in the string).