Longest repeating subsequence

Statement

Given a string s, find the length of the longest subsequence that appears at least twice in the string without reusing the same index.

Intuition

We want to find the Longest Common Subsequence (LCS) of the string with itself, but with the restriction that the indices must not be the same.

Key Idea:

Use a variation of LCS with the condition:
If characters match, they should be at different indices (i != j).

Recursive Approach

class Solution {
    int lrs(String s1, String s2, int i, int j) {
        if (i == 0 || j == 0) return 0;

        if (s1.charAt(i - 1) == s2.charAt(j - 1) && i != j) {
            return 1 + lrs(s1, s2, i - 1, j - 1);
        } else {
            return Math.max(lrs(s1, s2, i - 1, j), lrs(s1, s2, i, j - 1));
        }
    }

    int LongestRepeatingSubsequence(String s) {
        int n = s.length();
        return lrs(s, s, n, n);
    }
}

Time Complexity:

O(2^n) — Exponential

Memoization (Top-down DP)

class Solution {
    int[][] dp;

    int lrs(String s1, String s2, int i, int j) {
        if (i == 0 || j == 0) return 0;

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

        if (s1.charAt(i - 1) == s2.charAt(j - 1) && i != j) {
            return dp[i][j] = 1 + lrs(s1, s2, i - 1, j - 1);
        } else {
            return dp[i][j] = Math.max(lrs(s1, s2, i - 1, j), lrs(s1, s2, i, j - 1));
        }
    }

    int LongestRepeatingSubsequence(String s) {
        int n = s.length();
        dp = new int[n + 1][n + 1];

        for (int[] row : dp) Arrays.fill(row, -1);

        return lrs(s, s, n, n);
    }
}

Time Complexity: O(n^2)

Space Complexity: O(n^2)

Tabulation (Bottom-up DP)

class Solution {
    int LongestRepeatingSubsequence(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] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[n][n];
    }
}

Time and Space Complexity

Method Time Complexity Space Complexity
Recursion O(2^n) O(1)
Memoization O(n^2) O(n^2)
Tabulation O(n^2) O(n^2)

Dry Run

Example: s = "aab"

Comparing "aab" with itself:

i != j is checked:
LRS = "a" → appears twice at different indices.
Length = 1

Summary