Longest Repeating Subsequence

Longest Repeating Subsequence (LRS) asks: starting from a string s, align it against itself and find the longest chain of matched character positions where every matched pair (i, j) satisfies s[i] = s[j] and i ≠ j. It is computed as LCS(s, s) with one extra rule bolted onto the matching step: a match is only accepted when the two indices being compared differ, so a character is never matched to itself in the same step.

Important subtlety, not a footnote: the i ≠ j guard only forbids a single matched pair from using the same index twice within that pair. It does not guarantee that the two resulting "copies" of the answer are built from two globally disjoint sets of indices. A single index can legally appear in two different pairs across the chain — once as the earlier index of one pair, once as the later index of the next pair. When that happens, the DP's number is larger than the true "both copies use completely disjoint indices" answer. Concretely, for s = "ababa" this DP reports 3, but the true index-disjoint LRS is 2 (see the worked example below). Treat the classic DP as computing the longest chain of pairwise-differing matches, not literally "two disjoint occurrences" — many summaries of this problem use the latter phrase loosely, and it is only accurate when the matched chain happens not to reuse an index.

Recognize the pattern

• The problem talks about a "repeated", "duplicated", or "appears twice" subsequence/substring inside a single string.
• A non-self-match condition is stated: a character can't be matched to its own occurrence in the same step (i ≠ j).
• It smells exactly like LCS phrasing ("longest common subsequence of X and Y") except X and Y are the same string.
• Caution: if the problem explicitly demands two globally disjoint index sets (not just pairwise i ≠ j), verify with a small example like "ababa" before trusting the classic DP — see the subtlety above.

Brute force → optimal

Brute force: generate all 2ⁿ subsequences of the string, and for each check whether it can be found twice at disjoint index sets (itself an expensive search). This is exponential — infeasible beyond n≈20.

Optimal: treat it as LCS(s, s) where index i is compared against index j, but the recurrence only accepts a match when i ≠ j (otherwise every character trivially "matches itself" and the answer would degenerate to n). This is a direct, one-line modification of the classic LCS DP, so it inherits LCS's polynomial-time structure — but also inherits the reuse subtlety described above, since nothing in the recurrence tracks which indices have already been "spent".

Recurrence

Let s have length n, 1-indexed, and let dp[i][j] = length of the longest pairwise-differing matched chain using s[1..i] and s[1..j].

dp[i][j] =
  dp[i-1][j-1] + 1        if s[i] == s[j] and i != j
  max(dp[i-1][j], dp[i][j-1])   otherwise

base case: dp[0][*] = dp[*][0] = 0
answer: dp[n][n]

Complexity, derived

The DP table has (n+1)×(n+1) cells. Each cell does O(1) work (one comparison, one addition, one max). So time = O(n²) — n² cells × O(1) each, no hidden multiplicative factor. Space for the table is O(n²); since each row only depends on the row above, this can be compressed to O(n) with two rolling rows if only the length is needed (reconstructing the actual chain still needs the full table or extra bookkeeping).

Worked example — and the disjointness trap

s = "ababa" (n = 5): a(1) b(2) a(3) b(4) a(5). Full table, dp[i][j]:

Every cell here follows the recurrence exactly as written — no cell needs correcting. dp[5][5] = 3. Backtracking from (5,5) gives the matched chain (1,3), (2,4), (3,5) — exactly three matched pairs, each with i ≠ j, so the DP is not misapplied.

But look at index 3: it is the later index in pair (1,3) and the earlier index in pair (3,5). Reading first-coordinates {1,2,3} spells "aba"; reading second-coordinates {3,4,5} also spells "aba" — but both readings pass through index 3, so they are not disjoint. There is no way to pick 3+3 = 6 distinct indices out of a 5-character string, so a genuinely index-disjoint repeated subsequence of length 3 is impossible here. The true disjoint-index LRS of "ababa" is 2: for example "ab" at indices {1,2} and, separately, "ab" at indices {3,4}. The classic DP overcounts by one on this input precisely because its chain reused index 3.

Pitfalls

• Forgetting the i ≠ j guard collapses the problem to plain LCS(s,s), which always returns n (the whole string trivially matches itself).
• Assuming the DP guarantees globally disjoint index sets. It only guarantees i ≠ j within each matched pair; the same index can be the "later" partner of one pair and the "earlier" partner of the next, silently reusing a physical character. Always sanity-check against a small alternating string like "ababa" before relying on the disjointness framing.
• Off-by-one indexing errors when mixing 0-indexed strings with a 1-indexed DP table — always be explicit about which index the recurrence reads from.
• Confusing LRS with Longest Repeated Substring (contiguous, uses suffix arrays/trees) — LRS here is a subsequence, not required to be contiguous.
• Assuming reconstruction is free — recovering the actual chain needs backtracking through the table (or storing parent pointers), not just the length, and that reconstruction is exactly where the index-reuse issue becomes visible.

When to use / when not — trade-offs

Use the LCS(s,s)-with-guard DP when your problem's definition of "repeating subsequence" is genuinely "a chain of matched positions with i ≠ j at every step" — that is the classic interview/GFG-style framing, and the DP answers it exactly in O(n²) time/space for n up to a few thousand. Do not use it unmodified if the problem insists on two literally disjoint sets of indices for the two occurrences — as shown above, the plain DP can overcount on inputs like "ababa"; that stricter version needs additional bookkeeping (e.g. tracking which indices are consumed) and is a harder combinatorial problem, not a one-line tweak. For very large n, or when you only need duplicated substrings (contiguous), prefer a suffix array / suffix automaton approach (O(n log n)) instead — a different problem shape. If you only need to check existence of any repeated character, a frequency count suffices and the DP is overkill.

Java

public int longestRepeatingSubsequence(String s) {
    int n = s.length();
    int[][] dp = new int[n + 1][n + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i - 1) == s.charAt(j - 1) && i != j) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n][n]; // length of the pairwise-differing chain, not guaranteed index-disjoint
}

Takeaways

• LRS is LCS(s, s) plus a single guard: reject matches where the two indices are equal.
• That guard only constrains each pair individually — it does not stop the chain from reusing one index across two different pairs, so the DP's number can exceed the true index-disjoint answer (proof: s = "ababa" gives dp = 3 vs. true disjoint answer 2).
• Complexity is O(n²) time and O(n²) space (or O(n) space with row compression) directly from the n×n cell count.
• Do not confuse it with longest repeated substring — that is a contiguous-match problem solved with suffix structures, not this DP.

Recall: On s = "ababa", why does the matched chain (1,3), (2,4), (3,5) reuse index 3, and what does that imply about calling this DP's result "two disjoint occurrences"?

Pattern derived from the classic Longest Common Subsequence DP (Bellman-style tabulation), adapted with a non-self-match constraint. This is a standard interview variant (e.g., GeeksforGeeks, InterviewBit DP series); those sources typically describe it as finding a "repeating subsequence", and the i ≠ j guard is universal — the claim that it yields two globally disjoint index sets is a common but imprecise gloss, corrected in the worked example above.