53. Longest Repeating Subsequence

Given a string s, find the length of its longest subsequence that appears at least twice in s using different index positions for each occurrence (the same character at the same index cannot be reused across the two copies).

Input: The input is a single line containing the string s. Output: Print a single integer - the length of the longest repeating subsequence.

1 <= |s| <= 2000

Without the i != j restriction, comparing a string to itself would trivially just match every character with itself, giving an answer equal to the string's own length - the restriction is what makes this a genuinely different, harder question.

Find the longest subsequence of a string that appears TWICE within it, using genuinely different character positions each time (not reusing the exact same index for both copies). Brute force: Try every possible pair of subsequences (using two different sets of indices) directly and check if they're equal - this is exponential, completely impractical beyond tiny strings. Optimised: Reframing the problem as 'LCS of the string with itself, but forbidding matched-index pairs' lets you reuse the EXACT same DP recurrence as standard LCS, with just one small added condition (i != j) - no need to invent a new algorithm from scratch, just a clever adaptation of a known one.

Fill the same DP table iteratively from smaller indices upward instead of via recursion, avoiding recursion-call overhead and any risk of stack depth issues for |s| up to 2000. Furthermore, since row i of the table only ever depends on row i-1, there's no need to keep the full 2D table in memory - keep just two 1D rows (previous and current) and roll them forward as i increases, reading off the final answer once the last row is computed. This keeps the same O(n^2) time as the memoized version but reduces the memory footprint from quadratic to linear. Time: O(n^2) Space: O(n)

Define the recurrence LRS(i, j) comparing the string against itself: if s[i] == s[j] and i != j, this character can be part of a shared subsequence, so LRS(i,j) = 1 + LRS(i-1, j-1); otherwise LRS(i,j) = max(LRS(i-1, j), LRS(i, j-1)). Implemented as plain recursion with no memoization, this correctly enumerates the choices but recomputes the same (i, j) subproblems repeatedly through different recursive paths, causing exponential blowup. Time: O(2^n) (exponential) Space: O(n)

The recursion above only ever depends on the pair (i, j), so store each computed LRS(i, j) result in a memo table indexed by i and j (top-down memoization) so it is computed only once. Every distinct (i, j) pair, of which there are O(n^2), now does O(1) work beyond its two recursive lookups, turning the exponential brute force into a quadratic algorithm - a dramatic improvement given |s| can be up to 2000. Time: O(n^2) Space: O(n^2)

1. This is exactly the Longest Common Subsequence of the string WITH ITSELF, but with one extra rule: matching characters can't come from the same index in both copies. 2. Build a DP table dp[i][j] comparing the string against itself: if s[i-1] equals s[j-1] AND i is not equal to j, extend the match; otherwise take the best of skipping a character from either 'copy'. 3. The final answer is in the bottom-right cell of the table.

Time: O(n²) - filling the DP table, exactly like standard LCS, since the string is being compared against itself. Space: O(n²), for the DP table.

A string with all distinct characters (answer 0, no repeat possible); a string of all identical characters, which stresses the i != j index constraint; s up to length 2000, testing O(n^2) DP performance.

Be ready to immediately recognize and state the 'LCS of s with itself, forbidding i==j matches' framing - this is exactly the kind of pattern-recognition (spotting a known algorithm hiding inside a new-sounding problem) interviewers reward.