515. The Longest Repeating Subsequence
Print the length of the longest subsequence that appears TWICE in the string, using two selections of positions that never share an index. The two copies must be the same string.
aabebcdd -> 3 abd, twice, using different positions each time
abab -> 2 ab, once from positions 0,1 and once from 2,3
abc -> 0 no character repeats
## The trick
Take the longest common subsequence of the string WITH ITSELF, and forbid matching a position with itself:
``` dp[i][j] = LCS of s[0..i-1] and s[0..j-1], with the extra rule i != j
s[i-1] == s[j-1] and i != j -> dp[i][j] = dp[i-1][j-1] + 1 otherwise -> dp[i][j] = max( dp[i-1][j], dp[i][j-1] ) ```
The answer is dp[n][n].
## Why the i != j guard is the entire problem
Without it, dp[n][n] is the LCS of the string with itself, which is the whole string:
every position matches itself. abc would answer 3 instead of 0.
With it, a character can only be matched to an occurrence of the same character at a DIFFERENT position, which is precisely what "appears twice using disjoint positions" means.
That is why the guard sits on the diagonal and nowhere else, and it is worth pausing on: one comparison turns a trivial answer into the intended one.
## Why disjointness comes out for free
The guard only forbids i == j at the moment of a match. It does not obviously prevent
one selection from reusing a position the other used.
It does, and the reason is the structure of an LCS: the two selections are strictly
increasing index sequences i1 < i2 < ... and j1 < j2 < ... paired in order, and the
guard makes i_t != j_t for every t. Suppose i_t == j_u for some t != u. Since
both sequences pair up in order and each pair has i != j, the relative order of i_t
and j_t is the same for all t, so one whole sequence is elementwise below the other,
and an element of one cannot equal an element of the other.
Worth checking with aaaa, which answers 3: the two selections are positions
0,1,2 and 1,2,3, which do overlap as SETS. So disjointness is per PAIR, not per set,
and the statement says "never share an index" meaning at matched positions. That is the
convention every version of this problem uses, and it has to be stated.
## Boundaries
abc answers 0, and it is the case the missing guard gets wrong.
aa answers 1, the smallest positive case. aaaa answers 3.
abcabc answers 3: the whole of abc twice.
## Cost
Time O(n^2). Space O(n^2), reducible to O(n) with two rows.
Constraints - `1 ≤ length of s ≤ 1000` - `s` contains only lowercase letters
Input
The first line contains the string s, of lowercase letters.
Output
Print the length of the longest subsequence appearing twice at non-shared matched positions.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.