SyntaxPilot
Courses/Competitive Programming/Lesson 34

Competitive Programming · Lesson 34 of 90 · 11 min

DP 3: DP on subsequences and strings

queued

These are the notes for Competitive Programming episode 34, part three of the dynamic programming section. Asha and Rohan walked through the same mela and each wrote down the stalls they visited, in order. An original problem, Mela Walk, asks for the longest list of stalls both visited in the same order: the longest common subsequence (LCS). Greedy matching prints 1 instead of 4; trying all 2^n subsequences is right but gets TLE at 30 letters. The trick for strings is to look at two prefixes and only their last letters: if they match, take the diagonal + 1; otherwise drop one of them. The state is dp[i][j]; the 5000 × 5000 table becomes two rows. With three transitions (delete, insert, replace) the same table gives edit distance, the idea behind autocorrect. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

Asha's diary of mela stalls: bangles, aloo tikki, pani puri, chai, kulfi, written as one letter each: b a p c k. Rohan's diary: a p c k b. The longest list of stalls both visited in the same order, skipping any stalls but never reordering, is a p c k: 4 stalls. The same question appears in diff tools (which lines two files share), DNA comparison and plagiarism checkers.

What is a subsequence?

A subsequence is what's left after deleting some letters, keeping the rest in their original order. apk is a subsequence of bapck; kp is not (k comes after p). A substring is different: it must be contiguous (apc is a substring of bapck, apk is not). A string of length n has 2^n subsequences.

Problem K · Mela Walk

(Written for this course, in the style of an AtCoder Beginner Contest problem.)

Given two strings s and t of lowercase letters, print the length of their longest common subsequence.

  • Input: s on the first line, t on the second (1 ≤ |s|, |t| ≤ 5000).
  • Output: the LCS length.
Input Output
bapck / apckb 4 (apck)
masala / salaam 4 (sala)
pck / apckb 3 (pck)
abc / xyz 0

Attempt 1: greedy matching (wrong)

Walk through s; match each letter at the earliest place it appears in t after the previous match.

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    int pos = 0, len = 0;                 // next free position in t
    for (char c : s) {
        size_t k = t.find(c, pos);         // earliest match
        if (k != string::npos) { len++; pos = k + 1; }
    }
    cout << len << "\n";
    return 0;
}

Sample 1 prints 1 (expected 4). Greedy matched b first, but b is the last letter of t, so nothing can follow it. Sometimes skipping a letter is better than matching it; we need to try both.

Attempt 2: all 2^n subsequences (Time Limit Exceeded)

#include <bits/stdc++.h>
using namespace std;

bool isSub(const string& a, const string& t) {   // a inside t, in order?
    int j = 0;
    for (char c : t) if (j < (int)a.size() && a[j] == c) j++;
    return j == (int)a.size();
}

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    int best = 0;
    for (long long mask = 0; mask < (1LL << n); mask++) {   // every subsequence of s
        string a;
        for (int i = 0; i < n; i++) if (mask >> i & 1) a += s[i];
        if ((int)a.size() > best && isSub(a, t)) best = a.size();
    }
    cout << best << "\n";
    return 0;
}

Samples: 4, 4, correct. With 30 letters each it prints Time Limit Exceeded: 2^30 ≈ 10^9 subsequences, each built and checked.

The key idea: two prefixes, last letters

Take the first i letters of s and the first j letters of t. Look only at the last letter of each, s[i−1] and t[j−1]:

  • They are equal: match them. The answer is 1 + the LCS of the two shorter prefixes: dp[i−1][j−1] + 1.
  • They differ: at least one of them is not in the answer, so drop one: max(dp[i−1][j], dp[i][j−1]).

State: dp[i][j] = LCS of s[0..i) and t[0..j). Base: dp[0][j] = dp[i][0] = 0. Answer: dp[n][m]. Order: i increasing, j increasing. 25 million states for 5000 × 5000, O(1) each.

The indices: dp counts letters (i letters), the string counts from zero, so the last letter of the first i letters is s[i - 1].

The table on "pck" vs "apckb"

(empty) a p c k b
(empty) 0 0 0 0 0 0
p 0 0 1 1 1 1
c 0 0 1 2 2 2
k 0 0 1 2 3 3

Row p, column p: a match, diagonal 0 + 1 = 1. Row c, column k: c ≠ k, max(up 1, left 2) = 2. The answer, bottom right, is 3 (pck).

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    // dp[i][j] = LCS of the first i letters of s and the first j of t
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;    // match
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);           // drop one
        }
    cout << dp[n][m] << "\n";
    return 0;
}

Sample 1 prints 4. At 5000 × 5000 the table is 25 million ints, 100 MB.

Why one row fails, and why two rows work

Like last episode, try to keep one row:

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<int> dp(m + 1, 0);              // just one row?
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) dp[j] = dp[j - 1] + 1;
            else dp[j] = max(dp[j], dp[j - 1]);
        }
    cout << dp[m] << "\n";
    return 0;
}

On sample 2 (masala / salaam) it prints 5 (expected 4). The match needs the diagonal (the old dp[j−1]), but the left cell (the new dp[j−1]) has already overwritten it. No loop direction fixes this: the left value must be new and the diagonal must be old. So keep two rows:

  • prev = row i − 1 (gives the diagonal and the cell above), cur = row i (gives the cell on the left).
  • After each row, swap(prev, cur): swapping two vectors swaps their internal pointers, O(1).

Memory: 25 million ints (100 MB) → 2 × 5001 ints (about 40 KB).

The accepted solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<int> prev(m + 1, 0), cur(m + 1, 0);   // row i - 1 and row i
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) cur[j] = prev[j - 1] + 1;
            else cur[j] = max(prev[j], cur[j - 1]);
        }
        swap(prev, cur);
    }
    cout << prev[m] << "\n";
    return 0;
}
Input Output
sample 1 4
sample 2 4
abc / xyz 0
the 30-letter test that timed out 19 (instant)

The worst case, built inside main (two 5000-letter strings):

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 5000, m = 5000;                // worst case, built here
    string s, t;
    for (int i = 0; i < n; i++) s += "abc"[i % 3];
    for (int i = 0; i < m; i++) t += "cab"[i * 7 % 3];
    vector<int> prev(m + 1, 0), cur(m + 1, 0);   // row i - 1 and row i
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) cur[j] = prev[j - 1] + 1;
            else cur[j] = max(prev[j], cur[j - 1]);
        }
        swap(prev, cur);
    }
    cout << prev[m] << "\n";
    return 0;
}

Output: 4999, in a fraction of a second.

A stress test

Random strings over only 3 letters, so there are many matches:

#include <bits/stdc++.h>
using namespace std;

int brute(const string& s, const string& t) {
    int n = s.size(), best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        string a;
        for (int i = 0; i < n; i++) if (mask >> i & 1) a += s[i];
        int j = 0;
        for (char c : t) if (j < (int)a.size() && a[j] == c) j++;
        if (j == (int)a.size()) best = max(best, j);
    }
    return best;
}
int fast(const string& s, const string& t) {
    int n = s.size(), m = t.size();
    vector<int> prev(m + 1, 0), cur(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            cur[j] = s[i - 1] == t[j - 1] ? prev[j - 1] + 1 : max(prev[j], cur[j - 1]);
        swap(prev, cur);
    }
    return prev[m];
}
int main() {
    mt19937 rng(34);
    for (int t = 1; t <= 1000; t++) {
        string a, b;
        int n = rng() % 12 + 1, m = rng() % 12 + 1;
        for (int i = 0; i < n; i++) a += char('a' + rng() % 3);
        for (int i = 0; i < m; i++) b += char('a' + rng() % 3);
        if (brute(a, b) != fast(a, b)) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 1000 tests passed";
}

Output: all 1000 tests passed.

Variant: edit distance (autocorrect)

You type chiken; the phone suggests chicken. "Closest" means the fewest edits, where an edit is deleting a letter, inserting a letter, or replacing one. This count is the edit distance (also called the Levenshtein distance).

dp[i][j] = fewest edits to turn s[0..i) into t[0..j):

Move Cost
delete s[i−1] dp[i−1][j] + 1
insert t[j−1] dp[i][j−1] + 1
keep (equal) / replace (different) dp[i−1][j−1] + (s[i−1] ≠ t[j−1])

Base: dp[i][0] = i (delete everything), dp[0][j] = j (insert everything). These are not zero.

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    // dp[i][j] = fewest edits to turn s[0..i) into t[0..j)
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 0; i <= n; i++) dp[i][0] = i;        // delete all
    for (int j = 0; j <= m; j++) dp[0][j] = j;        // insert all
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = min({dp[i - 1][j] + 1,                 // delete s[i-1]
                            dp[i][j - 1] + 1,                 // insert t[j-1]
                            dp[i - 1][j - 1] + (s[i - 1] != t[j - 1])});   // keep / replace
    cout << dp[n][m] << "\n";
    return 0;
}
Input Output
chiken / chicken 1 (insert c)
paneer / panir 2 (replace one e with i, delete the other)

Complexity vs the constraints

Approach Time Memory Verdict
all subsequences O(2^n · (n + m)) O(n) TLE at n = 30
greedy matching O(n · m) O(1) wrong (1 vs 4)
full table O(n · m) = 2.5 · 10^7 100 MB accepted if the limit allows
two rows O(n · m) = 2.5 · 10^7 about 40 KB accepted

Common mistakes (and the real outputs)

Bug 1: one row when the transition needs the diagonal

Shown above: 5 instead of 4 on masala / salaam.

Bug 2: off-by-one indexing

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    // dp[i][j] = LCS of the first i letters of s and the first j of t
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (s[i] == t[j])         dp[i][j] = dp[i - 1][j - 1] + 1;    // match
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);           // drop one
        }
    cout << dp[n][m] << "\n";
    return 0;
}

On abc / xyz (no common letters) it prints 1 (expected 0). With i = 3, s[3] is past the last letter; a std::string keeps a hidden null character '\0' at s[size()], and t[3] is one too, so they "match". Every other comparison was shifted by one as well. dp counts letters; the string counts from zero: always s[i - 1] and t[j - 1].

Summary table

Mistake What you see Why Fix
match each letter as early as possible 1 instead of 4 an early match blocks the rest DP on two prefixes
one row: dp[j] = dp[j - 1] + 1 5 instead of 4 the diagonal is overwritten two rows, swap
if (s[i] == t[j]) 1 instead of 0 off by one, reads the hidden '\0' s[i - 1], t[j - 1]
edit distance with dp[i][0] = 0 too few edits i letters need i deletes dp[i][0] = i, dp[0][j] = j
full 5000 × 5000 table of long long 200 MB, may get MLE wrong type and size two rows of int

Mini project

Build a tiny "diff" tool: read two short texts line by line, compute the LCS of the two lists of lines (the same DP, comparing whole lines instead of letters), then walk back through the full table and print each line with (kept), - (only in the first text) or + (only in the second). This is how git diff and diff decide what changed.

Practice

  1. Print the LCS itself, not just its length.

    Answer Keep the full table and walk back from dp[n][m]: if s[i−1] = t[j−1], the letter is in the LCS, go diagonally; else move to the larger of up and left. Sample 1: <b>apck</b>; sample 2: <b>sala</b>.

  2. Shortest common supersequence: the shortest string that has both s and t as subsequences.

    Answer Its length is |s| + |t| − LCS: shared letters are written once. Sample 1: 5 + 5 − 4 = <b>6</b> (bapckb); sample 2: 6 + 6 − 4 = <b>8</b>.

  3. Longest palindromic subsequence of s.

    Answer LCS of s and reverse(s) (or an interval DP, next episode). <code>masala</code> → <b>3</b> (asa), <code>malayalam</code> → <b>9</b>, <code>biryani</code> → <b>3</b> (iri).

  4. Count the subsequences of s equal to t (mod 10^9 + 7).

    Answer ways[j] = number of ways to form t[0..j) so far, ways[0] = 1; for each letter c of s, for j from m down to 1, if t[j−1] = c then ways[j] += ways[j−1]. <code>banana</code>, <code>ana</code> → <b>4</b>.

Quick quiz

What is the LCS length of chai and achar?

A) 1 · B) 2 · C) 3 · D) 4

Answer

C. cha appears in order in both strings; there is no i in achar, so 4 is impossible.

Interview questions

  1. Subsequence vs substring? A subsequence keeps the order but may skip letters; a substring is contiguous. Longest common substring uses dp[i][j] = dp[i−1][j−1] + 1 on a match and 0 otherwise.
  2. What is the LCS recurrence? Match: dp[i−1][j−1] + 1; otherwise max(dp[i−1][j], dp[i][j−1]).
  3. How do you reduce LCS memory to O(m)? Two rows (prev and cur), since each cell needs the diagonal, the cell above and the cell on the left.
  4. What is edit distance, and where is it used? The fewest insertions, deletions and replacements to turn one string into another: spell checkers, autocorrect, DNA alignment, fuzzy search.
  5. Relation between LCS and edit distance? With only insertions and deletions allowed, the distance is |s| + |t| − 2 · LCS.
  6. Can LCS be solved faster than O(n · m)? Not in general for arbitrary strings (bitset tricks give about a 64× speed-up); for contests, n · m up to about 10^8 is the usual limit.

Glossary

Term Meaning Example
Subsequence Delete some letters, keep the order apk in bapck
Substring A contiguous piece apc in bapck
LCS Longest common subsequence bapck, apckb → apck
Prefix The first i letters ba is a prefix of bapck
State on two prefixes dp[i][j] for s[0..i) and t[0..j) the LCS table
Diagonal transition dp[i−1][j−1] + 1 on a match both last letters used
Two rows (rolling array) Keep only rows i − 1 and i prev, cur, swap
Edit distance (Levenshtein) Fewest insert / delete / replace edits chiken → chicken = 1
Null character The hidden '\0' at s[s.size()] the off-by-one bug
Greedy Take the locally best choice match the earliest letter
Stress test Fast vs brute force on random small tests all 1000 tests passed

Summary

  • Greedy matching fails (1 vs 4); all 2^n subsequences TLE at n = 30.
  • State dp[i][j] on two prefixes; look at the last letters: match → diagonal + 1, else max(up, left). O(n · m).
  • The diagonal makes one row fail (5 vs 4): keep two rows and swap, 100 MB → 40 KB.
  • Edit distance: delete, insert, keep/replace; base dp[i][0] = i, dp[0][j] = j.
  • Real bug: s[i] instead of s[i - 1] (1 instead of 0).

Solutions in C++, Java and Python

Problem K · Mela Walk

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<int> prev(m + 1, 0), cur(m + 1, 0);   // row i - 1 and row i
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) cur[j] = prev[j - 1] + 1;
            else cur[j] = max(prev[j], cur[j - 1]);
        }
        swap(prev, cur);
    }
    cout << prev[m] << "\n";
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine() + " " + br.readLine());
        String s = st.nextToken(), t = st.nextToken();
        int n = s.length(), m = t.length();
        int[] prev = new int[m + 1], cur = new int[m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) cur[j] = prev[j - 1] + 1;
                else cur[j] = Math.max(prev[j], cur[j - 1]);
            }
            int[] tmp = prev; prev = cur; cur = tmp;
        }
        System.out.println(prev[m]);
    }
}

Python (fine for the samples; 2.5 · 10^7 steps in pure Python is slow, so use C++ in contests)

import sys

def main():
    s, t = sys.stdin.read().split()
    m = len(t)
    prev = [0] * (m + 1)
    for ch in s:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == t[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = prev[j] if prev[j] > cur[j - 1] else cur[j - 1]
        prev = cur
    print(prev[m])

main()

Next episode: DP 4: interval DP (dp[l][r] on ranges, filled by length).