Longest Repeating Subsequence

 Given string str, find the length of the longest repeating subsequence such that it can be found twice in the given string.

The two identified subsequences A and B can use the same ith character from string s if and only if that ith character has different indices in A and B. For example, A = "xax" and B = "xax" then the index of the first "x" must be different in the original string for A and B.

Examples :

Input: s = "axxzxy"

Output: 2

Explanation: The given array with indexes looks like

a x x z x y 

0 1 2 3 4 5

The longest subsequence is "xx". It appears twice as explained below.

subsequence A

x x

0 1  <-- index of subsequence A

------

1 2  <-- index of s

subsequence B

x x

0 1  <-- index of subsequence B

------

2 4  <-- index of s

We are able to use character 'x' (at index 2 in s) in both subsequences as it appears on index 1 in subsequence A and index 0 in subsequence B.

Input: s = "axxxy"

Output: 2

Explanation: The given array with indexes looks like

a x x x y 

0 1 2 3 4

The longest subsequence is "xx". It appears twice as explained below.

subsequence A

x x

0 1  <-- index of subsequence A

------

1 2  <-- index of s

subsequence B

x x

0 1  <-- index of subsequence B

------

2 3  <-- index of s

We are able to use character 'x' (at index 2 in s) in both subsequencesas it appears on index 1 in subsequence A and index 0 in subsequence B.

Constraints:

1 <= s.size() <= 10^3

📘 Quick Notes for Revision

• Problem: Find length of the longest subsequence that appears at least twice in the string.

• Approach:

  • Treat it like Longest Common Subsequence (LCS) of the string with itself.

  • Add condition: indices i != j so we don’t reuse the same character.

• DP State:

  • dp[i][j] → length of LRS in substrings s[i…] and t[j…].

• Recurrence:

  • If s[i] == t[j] and i != j → 1 + solve(i+1, j+1)

  • Else → max(solve(i+1, j), solve(i, j+1))

• Time Complexity: O(n²)

• Space Complexity: O(n²) (can optimize to O(n) if bottom‑up).

// User function Template for Java

class Solution {

   

    // Recursive helper function with memoization

    // i, j → current indices in s and t

    // n1, n2 → lengths of the strings

    // s, t   → strings we are comparing (in this problem both are same)

    // dp     → memoization table to store already computed results

    public static int solve(int i, int j, int n1, int n2, String s, String t, int [][] dp) {

       

        // Base case: if we reach the end of either string, no subsequence left

        if (i >= n1 || j >= n2) {

            return 0;

        }

       

        // If this state is already computed, return its result

        if (dp[i][j] != -1) {

            return dp[i][j];

        }

       

        // Case 1: Characters match and indices are different

        // We include this character in the repeating subsequence

        if (s.charAt(i) == t.charAt(j) && i != j) {

            dp[i][j] = 1 + solve(i + 1, j + 1, n1, n2, s, t, dp);

        }

        // Case 2: Characters don't match OR indices are same

        // We skip one character either from s or from t and take the best result

        else {

            dp[i][j] = Math.max(

                solve(i + 1, j, n1, n2, s, t, dp), // skip char from s

                solve(i, j + 1, n1, n2, s, t, dp)  // skip char from t

            );

        }

       

        // Return the computed answer for this state

        return dp[i][j];

    }

   

    // Main function to be called

    public int LongestRepeatingSubsequence(String s) {

        int n1 = s.length();

        int n2 = s.length();

       

        // Initialize dp table with -1 (meaning "not calculated yet")

        int [][] dp = new int[n1][n2];

        for (int [] row : dp) {

            Arrays.fill(row, -1);

        }

       

        // Start recursion from index 0,0

        return solve(0, 0, n1, n2, s, s, dp);

    }

}