Longest Repeating Subsequence

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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];
}