How to Find the Longest Repeating Subsequence in a String

Introduction

The Longest Repeating Subsequence (LRS) problem is a classic dynamic programming problem that asks for the longest subsequence in a string that appears at least twice, but the repeated subsequences must not use the same character index both times. This problem is similar to the Longest Common Subsequence (LCS), with the added condition that the same index cannot be reused.

Problem Statement

Given a string, find the length of the longest subsequence that occurs at least twice in the string and where the two subsequences do not share the same character index at any position.

For example, in the string “aab”, the answer is 1, since “a” is the longest repeating subsequence (the first and second as).

Approach

The solution is based on dynamic programming, similar to LCS. We define a 2D array dp where dp[i][j] stores the length of the longest repeating subsequence in the first i characters compared with the first j characters of the string. While building the table, we must ensure that the indices i and j are not the same to avoid counting the same character instance twice.

The recurrence relation is as follows:

• If s.charAt(i - 1) == s.charAt(j - 1) and i != j, then dp[i][j] = 1 + dp[i - 1][j - 1]
• Otherwise, dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

Java Implementation

public class LongestRepeatingSubsequence {

    public static int findLongestRSLength(String inputString) {
        int N = inputString.length();
        int[][] dpArray = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (inputString.charAt(i - 1) == inputString.charAt(j - 1) && i != j) {
                    dpArray[i][j] = 1 + dpArray[i - 1][j - 1];
                } else {
                    dpArray[i][j] = Math.max(dpArray[i - 1][j], dpArray[i][j - 1]);
                }
            }
        }

        return dpArray[N][N];
    }

    public static void main(String[] args) {
        String inputString = "aab";
        int len = findLongestRSLength(inputString);
        System.out.println("Length of LRS: " + len);
    }
}

Explanation of the Example

In the input string "aab", the function builds a DP table and computes the length of the LRS. It identifies that the two “a”s can form a valid repeating subsequence (without using the same index). Thus, the result is 1.

Time and Space Complexity

The time complexity is O(n^2) where n is the length of the input string, as we fill a 2D table. The space complexity is also O(n^2) due to the DP table.

Conclusion

The Longest Repeating Subsequence problem is a useful variation of the Longest Common Subsequence. Understanding how to modify the LCS logic to respect index constraints is key to solving it. Using dynamic programming ensures an efficient solution for this otherwise exponential problem.

You can find the example code on Github.