DP on Treesstringoptimization

Longest repeating and non-overlapping substring

Given a string, find the length of the longest substring that occurs at least twice within it, where the two occurrences do not overlap each other in position.

Note. Listed under DP on Trees in the course's source list, but the recurrence compares two positions within one string, making it a stringPair2d problem rather than a tree DP.

Do this lesson first: longest common subsequence

Example input

s = "abababab"

Expected output

4

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][j], for i < j, is the length of the longest run of letters that ends exactly at letter i AND ends exactly at letter j, capped at j - i so that the copy ending at letter i finishes before the copy ending at letter j begins. Put another way, it is the longest common suffix of s's first i letters and its first j letters, clipped to the gap between their ends. The two axes are the same string: s is the first n letters of abababab, n = 8 at the drive size, the row index says where the earlier copy ends and the column index says where the later copy ends. Row i's own letter is s[i - 1] and column j's is s[j - 1], which is why row 4's gutter reads 4 b. A pair with i > j names the same two copies as (j, i) with their roles swapped, so it is not a separate state, and those cells are left out of the table. dp[4][8] = 4 says that the four letters ending at letter 4 and the four ending at letter 8 agree, abab both times, and that the two copies, letters 1 to 4 and 5 to 8, do not overlap. It says nothing about a run that ends anywhere else.

dp[i][j] = min(dp[i - 1][j - 1] + 1, j - i) if s[i - 1] = s[j - 1], else 0 (for i < j)

A repeated run that ends at this pair has to use both last letters, s[i - 1] and s[j - 1]. If they differ, no run ends on this pair and the cell is 0. If they match, the run is this pair glued to the run that ended one letter earlier at both places, dp[i - 1][j - 1] + 1, the same step longest-common-substring takes. What is new is the cap. A copy of length k ending at letter j covers letters j - k + 1 to j, and the earlier copy ends at letter i, so the two do not overlap exactly when j - k + 1 > i, which is k <= j - i. So the cell keeps the smaller of the extended run and the gap: min(dp[i - 1][j - 1] + 1, j - i). Capping, rather than throwing the run away, loses nothing: if the k letters ending at letter i and the k ending at letter j agree, so do the last j - i of each, and those two copies fit. The cap also passes down a diagonal intact, because j - i is the same number at each cell of one diagonal; once a run reaches its diagonal's gap, the cell stays at the gap for as long as the letters keep matching. The gap is read off the cell's own coordinates, not out of another cell.

Two kinds of base, both 0. Row 0, across columns 0 to n: the earlier prefix is empty, so it has no letter to end a run on. The main diagonal, dp[i][i] for i from 1 to n: a letter set against itself, where the gap j - i is 0, so the cap leaves no room for a run of even one letter. At the drive size that is 9 bases in row 0 and 8 on the diagonal, 17 in all. The cells below the diagonal are left out, which is why column 0 holds only dp[0][0] and row n holds only dp[n][n]. No computed cell reads a diagonal base: a cell (i, j) with j > i reads at most dp[i - 1][j - 1], whose column is still ahead of its row, so that cell sits in row 0 or above the diagonal. The diagonal bases are in the table to say what the pair (i, i) is, not to feed anything. Row 0 is read in only a few places: dp[0][j] is read only by dp[1][j + 1], and only when letter 1 matches letter j + 1, which at the drive size means dp[0][2], dp[0][4] and dp[0][6]. A row-major sweep, left to right within each row, finishes the previous row before it starts the next, so the diagonal neighbour is final whenever a match needs it, and a mismatch needs nothing. As on longest-common-substring, the answer is the largest cell anywhere, not the last one; here the last cell, dp[n][n], is a diagonal base and holds 0 at every size.

Tabulation over the upper triangle. At the drive size that is 17 bases and 28 computed cells, 45 of the 81 cells the square declares, and 16 of the 28 are mismatches that write 0 without consulting a neighbour. As on longest-common-substring, a memoized top-down solve saves nothing, since the answer is the largest cell anywhere and so each cell has to be asked about. Space shrinks the same two ways as well. A computed cell depends only on its diagonal, and a diagonal has one fixed gap, so a counter that walks one diagonal, resets on a mismatch and never passes that diagonal's gap reproduces its cells in O(1) space; the computed cells lie on n - 1 diagonals, one per gap from 1 to n - 1. Or keep a single row and sweep it right to left, so that dp[i - 1][j - 1] still holds the previous row's value when j comes down to it. Drag the slider and the string grows one letter at a time on both axes; the answer goes 2, 2, 2, 3, 4 across lengths 4 to 8. At length 4, abab, the run ab at letters 1 to 2 recurs at letters 3 to 4, so dp[2][4] = 2. Lengths 5 and 6 bring longer repeats, but in each of them the two copies overlap, and the cap holds them at 2. At length 5, aba ends at letters 3 and 5 but the two copies share letter 3, so dp[3][5] is capped at 2 and ties dp[2][4]. At length 6, four cells hold 2. At length 7 a three-letter repeat finally fits, aba at letters 1 to 3 and 5 to 7, so dp[3][7] = 3, and at length 8 abab at letters 1 to 4 and 5 to 8 gives dp[4][8] = 4.

Time O(n^2)Space O(n^2), reducible to O(n) with one row swept right to left, or O(1) by walking each diagonal with a counter capped at that diagonal's gap

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Two kinds of base, both 0. Row 0, across columns 0 to n: the earlier prefix is empty, so it has no letter to end a run on. The main diagonal, dp[i][i] for i from 1 to n: a letter set against itself, where the gap j - i is 0, so the cap leaves no room for a run of even one letter. At the drive size that is 9 bases in row 0 and 8 on the diagonal, 17 in all. The cells below the diagonal are left out, which is why column 0 holds only dp[0][0] and row n holds only dp[n][n]. No computed cell reads a diagonal base: a cell (i, j) with j > i reads at most dp[i - 1][j - 1], whose column is still ahead of its row, so that cell sits in row 0 or above the diagonal. The diagonal bases are in the table to say what the pair (i, i) is, not to feed anything. Row 0 is read in only a few places: dp[0][j] is read only by dp[1][j + 1], and only when letter 1 matches letter j + 1, which at the drive size means dp[0][2], dp[0][4] and dp[0][6]. A row-major sweep, left to right within each row, finishes the previous row before it starts the next, so the diagonal neighbour is final whenever a match needs it, and a mismatch needs nothing. As on longest-common-substring, the answer is the largest cell anywhere, not the last one; here the last cell, dp[n][n], is a diagonal base and holds 0 at every size.

Rows ↓
Cols →

∅

1 a

2 b

3 a

4 b

5 a

6 b

7 a

8 b

∅

0

1 a

·

0

1

0

1

0

1

0

2 b

·

0

2

0

2

0

2

3 a

·

0

2

0

3

0

4 b

·

0

2

0

4

5 a

·

0

2

0

6 b

·

0

2

7 a

·

0

8 b

·

0

Rows ↓s, the first n letters of abababab: the earlier copy ends at letter i

Cols →s again: the later copy ends at letter j

longest-repeating-non-overlapping-substring.ts

1function longestRepeatingNonOverlapping(s) {
2 const n = s.length;
3 const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
4 let best = 0;
5 for (let i = 1; i <= n; i++) {
6 for (let j = i + 1; j <= n; j++) {
7 dp[i][j] = s[i - 1] === s[j - 1]
8 ? Math.min(dp[i - 1][j - 1] + 1, j - i)
9 : 0;
10 best = Math.max(best, dp[i][j]);
11 }
12 }
13 return best;
14}

Base caseComputedBeing readAnswer

The code, the trap, the variations

longest-repeating-non-overlapping-substring.ts

1function longestRepeatingNonOverlapping(s) {
2 const n = s.length;
3 const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
4 let best = 0;
5 for (let i = 1; i <= n; i++) {
6 for (let j = i + 1; j <= n; j++) {
7 dp[i][j] = s[i - 1] === s[j - 1]
8 ? Math.min(dp[i - 1][j - 1] + 1, j - i)
9 : 0;
10 best = Math.max(best, dp[i][j]);
11 }
12 }
13 return best;
14}

Where people go wrong

Dropping the cap: writing dp[i - 1][j - 1] + 1 on a match, as longest-common-substring does. That table measures the longest substring that occurs twice with overlap allowed, and on this string overlapping repeats are common: it returns 2, 3, 4, 5, 6 across lengths 4 to 8 against the correct 2, 2, 2, 3, 4, right only at length 4. At length 8 it returns 6, from dp[6][8], for ababab at letters 1 to 6 and again at letters 3 to 8, two copies that share letters 3 to 6. The cap and the j > i bound each keep a letter from counting as a repeat of itself, and either one alone is enough: with the cap, dp[i][i] = min(dp[i - 1][i - 1] + 1, 0) = 0, and with the bound the main diagonal is never computed. Drop both, letting j start at i rather than i + 1 with no cap, and the main diagonal climbs dp[i][i] = i, reporting the whole string, 8 letters at length 8, as its own repeat. The third trap is longest-common-subsequence's habit of returning the last cell; here that is dp[n][n], a diagonal base, which gives 0 at every length.

Write 0 instead of capping when the extended run would overlap, a form common in published solutions: dp[i][j] = dp[i - 1][j - 1] + 1 if the letters match and dp[i - 1][j - 1] < j - i, else 0.
Only the match branch changes; the bases, the left-out lower triangle, the single diagonal read and the row-major sweep stay as they are. Individual cells do come out differently. At the drive size three of them do: along the gap-2 diagonal this page writes 1, 2, 2, 2, 2, 2 where the reset form writes 1, 2, 0, 1, 2, 0, counting up to the gap, dropping to 0 rather than going past it, and starting over. The answer does not change: measured at each slider length, both forms give 2, 2, 2, 3, 4. That is not luck of this string. Both tables hold 0 on the cell just before a run of matching pairs starts, a mismatch or a row-0 base. From there the reset form never writes more than this page does: it extends only while its diagonal neighbour is below the gap, so what it writes stays within the gap, and that neighbour is no larger than this page's, so it stays within this page's extended run as well. On a run of matching pairs it counts 1, 2, 3 and so on until it reaches the gap or the run ends, which is exactly the largest value this page writes on that run. So each diagonal's largest cell is the same number in both tables.
Return the repeated substring itself, not just its length.
The table, its recurrence and its bases do not change; the running best also records the cell (i, j) where it was found. A run is contiguous, so its end and its length pin it down: the substring is letters i - best + 1 to i, and its second copy is letters j - best + 1 to j. At the drive size that is dp[4][8] = 4, abab at letters 1 to 4 and 5 to 8. A tie needs a rule, and this string produces ties: at length 6 four cells hold the maximum, 2, namely dp[2][4], dp[2][6], dp[3][5] and dp[4][6]. Keeping the first one in row-major order, as this page's answer cell does, reports ab at letters 1 to 2 and 3 to 4; dp[3][5] would report ba, at letters 2 to 3 and 4 to 5.

Max Height of Tree when any Node can be Root