Longest Repeated Subsequence

Problem Statement

Given a string, find the length of the longest subsequence that appears at least twice in the string. The two occurrences must use characters at different positions (same index cannot be used for both).

Example:

• Input: s = "axxzxy"
• Output: 2 (the repeated subsequence is "xx" — using positions 1,2 for one and positions 1,4 or 2,4 for another)

Noob-Friendly Explanation

Imagine you write down a word and want to find the longest "pattern" that shows up twice inside it, but you can't reuse the same letter position for both copies. It's like a hidden message that appears twice! For "axxzxy", the pattern "xx" appears twice using different letter positions. This is just like finding the LCS of a string with itself, but we add a rule: the same position can't be used in both copies.

Approach 1: Brute Force (Recursion)

Intuition

This is similar to LCS, but applied to the same string twice. The only extra condition: when characters match, they must be at different indices.

Algorithm

1. Compare string with itself using two pointers i, j
2. If characters match AND i ≠ j, include them
3. Otherwise, try skipping from either side

public class Solution {
    public int lrs(String s, int i, int j, int n) {
        if (i == n || j == n) return 0;

        // Characters match and are at different positions
        if (s.charAt(i) == s.charAt(j) && i != j) {
            return 1 + lrs(s, i + 1, j + 1, n);
        }

        return Math.max(lrs(s, i + 1, j, n), lrs(s, i, j + 1, n));
    }

    public int longestRepeatedSubseq(String s) {
        return lrs(s, 0, 0, s.length());
    }
}

Complexity Analysis

• Time Complexity: O(2^(2n)) - Each call can branch into 2, with depth up to 2n
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Optimal (Bottom-Up DP)

Intuition

Same as LCS of the string with itself, but the matching condition requires i ≠ j. Build a 2D table where dp[i][j] is the LRS length considering first i chars (copy 1) and first j chars (copy 2).

Algorithm

1. Create dp[n+1][n+1] initialized to 0
2. If s[i-1] == s[j-1] and i != j: dp[i][j] = dp[i-1][j-1] + 1
3. Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
4. Answer is dp[n][n]

public class Solution {
    public int longestRepeatedSubseq(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];
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - Two nested loops of size n
• Space Complexity: O(n^2) - The 2D DP table