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
-
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>. -
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>. -
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). -
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
- 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.
- What is the LCS recurrence? Match: dp[i−1][j−1] + 1; otherwise max(dp[i−1][j], dp[i][j−1]).
- 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.
- 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.
- Relation between LCS and edit distance? With only insertions and deletions allowed, the distance is |s| + |t| − 2 · LCS.
- 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 (
1vs4); 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 (
5vs4): 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 ofs[i - 1](1instead of0).
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).