[CodeChef] Starters 71 — Maximizing LCS: index the DP by length and the base cases disappear
Published 7 October 2026
Problem: CodeChef — Maximizing LCS (Starters 71, difficulty 1567).
Alice and Bob share a string \(S\) of length \(N\) and each start with an empty string. They alternate, Alice first. On her turn Alice removes a prefix of \(S\) and appends it to her string. On his turn Bob removes a suffix of \(S\), reverses it, and appends it to his string. Prefixes and suffixes may be empty. Find the largest possible length of the LCS of their two strings.
Constraints: \(\sum N \le 5000\).
The idea is quick. The interesting part of this post is the implementation. My first draft of the DP was messy, and indexing the table by length instead of by position cleans it up.
Every game is one split¶
Alice always takes from the front and Bob always takes from the back, so their pieces never interleave. Whatever happens over many turns, once \(S\) is empty:
- Alice’s string is her pieces in order, which is one prefix \(S[0:k]\).
- Bob’s string is his pieces in the order he took them, each reversed. He takes the back first, so that’s \(\text{reverse}(S[k:N])\).
And any \(k\) is reachable in one round: Alice takes \(S[0:k]\), Bob takes the rest. So the answer is
One table for all the splits¶
Let \(T = \text{reverse}(S)\). Then \(\text{reverse}(S[k:N])\) is exactly the first \(N - k\) characters of \(T\). For \(S = \texttt{abccda}\), \(T = \texttt{adccba}\), and with \(k = 3\): \(\text{reverse}(\texttt{cda}) = \texttt{adc} = T[0:3]\).
So every split asks for the LCS of a prefix of \(S\) and a prefix of \(T\). The standard LCS table already holds the LCS of every pair of prefixes, so one \(O(N^2)\) table answers all \(N + 1\) splits. Running a separate LCS for each \(k\) would be \(O(N^3)\).
My first draft¶
n = len(s)
dp = [[0]*n for _ in range(n)]
# base case
dp[0][0] = 1 if s[0] == t[0] else 0
t = reversed(s)
for i in range(1, n):
for j in range(1, n):
dp[i][j] = dp[i-1][j-1] + 1 if S[i-1] == revS[j-1]
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) otherwise
Several things are off, and most of them come from one choice: dp[i][j] here is indexed by
position. It means “LCS of s[0..i] and t[0..j], both inclusive”.
- The base case is too small. With position indexing, row
0and column0aren’t trivial.dp[0][j]is \(1\) ifs[0]appears anywhere int[0..j], anddp[i][0]is similar. Setting onlydp[0][0]leaves the rest of row 0 and column 0 at \(0\), and the loops starting at1never fix them. - The indices don’t match the meaning. If
dp[i][j]covers positioni, the character to compare iss[i], nots[i-1]. Comparings[i-1]is what the length version does. I had mixed the two. - There’s no row for an empty prefix. The splits \(k = 0\) (Alice takes nothing) and \(k = N\) (Bob takes nothing) need the LCS with an empty string. An \(n \times n\) table indexed by position has no cell for “zero characters”. Those two splits always give \(0\) so they don’t change this answer, but the table can’t express them, and in other problems that matters.
t = reversed(s)gives an iterator, not a string, sot[j]fails. Uses[::-1]. It’s also used before it’s defined.
What fixing it in place looks like¶
Keep position indexing and handle the edges properly, and you need guards on every look-back:
for i in range(n):
for j in range(n):
if s[i] == t[j]:
dp[i][j] = (dp[i-1][j-1] if i > 0 and j > 0 else 0) + 1
else:
up = dp[i-1][j] if i > 0 else 0
left = dp[i][j-1] if j > 0 else 0
dp[i][j] = max(up, left)
It’s correct, but every read needs an “is this in range?” check. Each one is a chance to get an
off-by-one wrong. And reading the splits off it is awkward: \(S[0:k]\) is row k-1, \(T[0:N-k]\) is
column N-k-1, and \(k = 0\) or \(k = N\) need special cases.
The fix: index by length¶
Make the table \((N+1) \times (N+1)\) and change what the indices mean:
dp[i][j]= LCS length of the firsticharacters ofsand the firstjcharacters oft.
Now i = 0 means “the empty prefix”, which is a real state. The LCS of anything with an empty
string is \(0\), and that’s already what [0] * (n + 1) puts there. Row 0 and column 0 are the base
case, and the allocation fills them in for free.
The last character of a length-i prefix is s[i - 1]. That’s where the i - 1 comes from, and in
this version it’s correct. The recurrence:
The loops run i, j from 1 to n, so i - 1 and j - 1 are always at least 0. Every
look-back lands either in a computed cell or in the zero row/column. No guards are needed.
def max_lcs(s):
n = len(s)
t = s[::-1]
# dp[i][j] = LCS length of s[:i] and t[:j]
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, n + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# Alice takes s[:k]; Bob gets reverse(s[k:]), which is t[:n-k].
return max(dp[k][n - k] for k in range(n + 1))
The answer line also reads directly off the definition. Alice has \(k\) characters and Bob has
\(N - k\), so it’s dp[k][n - k]. \(k = 0\) and \(k = N\) are just cells in the zero row and column.
Side by side:
Position-indexed n × n |
Length-indexed (n+1) × (n+1) |
|
|---|---|---|
dp[i][j] means |
LCS of s[0..i], t[0..j] inclusive |
LCS of s[:i], t[:j] |
| Empty prefix | no cell | row/column 0 |
| Base case | fill row 0 and column 0 by hand, or guard every read | already zeros |
| Character compared | s[i], t[j] |
s[i-1], t[j-1] |
Answer for split k |
dp[k-1][n-k-1], plus special cases |
dp[k][n-k] |
The general rule: when a DP is over prefixes, index by prefix length and allocate one extra row
and column. The empty prefix becomes a real state, the base case is the zero-initialised border,
and the recurrence has no branches for edges. The same trick works for edit distance, subsequence
counting, knapsack (“first i items”), and so on.
Walkthrough on abccda¶
\(S = \texttt{abccda}\), \(T = \texttt{adccba}\). The answer cells dp[k][6 - k]:
| \(k\) | Alice \(S[0:k]\) | Bob \(T[0:6-k]\) | LCS |
|---|---|---|---|
| 0 | (empty) | adccba |
0 |
| 1 | a |
adccb |
1 |
| 2 | ab |
adcc |
1 |
| 3 | abc |
adc |
2 |
| 4 | abcc |
ad |
1 |
| 5 | abccd |
a |
1 |
| 6 | abccda |
(empty) | 0 |
The maximum is \(2\) at \(k = 3\), which matches the sample (abc and adc share ac).
Full solution¶
\(O(N^2)\) time per test. With \(\sum N \le 5000\) that’s \(2.5 \cdot 10^7\) cell updates at most. The statement asks for PyPy and fast I/O.
import sys
data = sys.stdin.buffer.read().split()
tests = int(data[0])
out = []
pos = 1
for _ in range(tests):
n = int(data[pos])
s = data[pos + 1].decode()
pos += 2
t = s[::-1]
# dp[i][j] = LCS length of s[:i] and t[:j]
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, n + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# Alice takes s[:k]; Bob gets reverse(s[k:]), which is t[:n-k].
out.append(str(max(dp[k][n - k] for k in range(n + 1))))
sys.stdout.write("\n".join(out))
Memory is \((N+1)^2\) ints, about \(2.5 \cdot 10^7\) for \(N = 5000\). That fits in the 1.5 GB limit. You
could keep only two rows, since each answer dp[k][n - k] sits in row k and can be read as soon as
that row is done, but at this size it isn’t needed.
I checked it on the samples (1 2 2), and against a brute force that plays out every possible
multi-turn game on 200 random strings over abc of length up to 5.
What I took away¶
- Alice from the front, Bob from the back means the turns don’t matter. The whole game is one split point \(k\).
- “Reverse of a suffix of \(S\)” is “a prefix of \(\text{reverse}(S)\)”. That turns \(N + 1\) separate LCS problems into one table.
- Index prefix DPs by length. The
+1row and column make the empty prefix a real state, so the base case comes from zero-initialisation and the recurrence needs no edgeifs.