Longest Repeating Subsequence
Problem
Return the length of the longest subsequence that appears at least twice in the string, where the two occurrences never use the same index at the same position.
Example 1
Input: "axxxy" Output: 2
"xx" can be formed from indices (1,2) and again from (2,3).
Also asked as: Find Longest Recurring Subsequence in String · Longest Repeated Subsequence
Test cases
Case 1
Input: "axxxy" Expected: 2
Case 2
Input: "aabb" Expected: 2
Case 3
Input: "aab" Expected: 1
Case 4
Input: "abc" Expected: 0
View solutionHide solution1 approach
1. LCS of the string with itself (excluding equal indices)
Time O(n²)Space O(n²)
Run the LCS DP on (s, s) but only count a match when the two indices differ.
function longestRepeatingSubseq(s) { const n = s.length; const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0)); for (let i = 1; i <= n; i++) for (let j = 1; j <= n; j++) dp[i][j] = s[i - 1] === s[j - 1] && i !== j ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]); return dp[n][n];}