StringProblem 9 of 43

Find Longest Recurring Subsequence in String

Brute Force
Time: O(2ⁿ)
Space: O(n)
Optimal
Time: O(n²)
Space: O(n²)

Problem Statement

Given a string, find the length of the longest recurring subsequence, such that the two subsequences don't have the same character at the same position. In other words, find the longest subsequence that appears at least twice in the string.

Example:

  • Input: "AABEBCDD"

  • Output: 3

  • Explanation: The longest recurring subsequence is "ABD" (positions: 0,2,6 and 1,4,7)

  • Input: "aabb"

  • Output: 2

  • Explanation: The longest recurring subsequence is "ab" (or "ab")

Approach 1: Brute Force (Generate All Subsequences)

Intuition

Generate all possible subsequences and check for each pair if they are equal and don't share the same position for any character.

Algorithm

  1. Generate all 2^n subsequences with their positions
  2. For each pair of subsequences, check if they are equal
  3. Ensure no character uses the same position in both
  4. Track the maximum length
java
import java.util.*;

public class Solution {
    private List<String> subsequences = new ArrayList<>();
    private List<List<Integer>> positionsList = new ArrayList<>();
    
    public int longestRecurringSubseq(String s) {
        generateSubsequences(s, 0, "", new ArrayList<>());
        
        int maxLen = 0;
        
        for (int i = 0; i < subsequences.size(); i++) {
            for (int j = i + 1; j < subsequences.size(); j++) {
                if (subsequences.get(i).equals(subsequences.get(j)) &&
                    noCommonPosition(positionsList.get(i), positionsList.get(j))) {
                    maxLen = Math.max(maxLen, subsequences.get(i).length());
                }
            }
        }
        
        return maxLen;
    }
    
    private void generateSubsequences(String s, int index, String current, 
                                       List<Integer> positions) {
        if (index == s.length()) {
            if (!current.isEmpty()) {
                subsequences.add(current);
                positionsList.add(new ArrayList<>(positions));
            }
            return;
        }
        
        generateSubsequences(s, index + 1, current, positions);
        
        positions.add(index);
        generateSubsequences(s, index + 1, current + s.charAt(index), positions);
        positions.remove(positions.size() - 1);
    }
    
    private boolean noCommonPosition(List<Integer> pos1, List<Integer> pos2) {
        for (int i = 0; i < pos1.size(); i++) {
            if (pos1.get(i).equals(pos2.get(i))) return false;
        }
        return true;
    }
}

Complexity Analysis

  • Time Complexity: O(2^n × 2^n) - Comparing all pairs of subsequences
  • Space Complexity: O(2^n × n) - Storing all subsequences with positions

Approach 2: Optimal (Dynamic Programming - LCS Variation)

Intuition

This problem is a variation of the Longest Common Subsequence (LCS) problem. We find LCS of the string with itself, but with the constraint that characters at the same position cannot be matched.

The recurrence relation is:

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

Algorithm

  1. Create a 2D DP table of size (n+1) × (n+1)
  2. Fill the table using the modified LCS recurrence
  3. dp[n][n] contains the answer
java
public class Solution {
    public int longestRecurringSubseq(String s) {
        int n = s.length();
        
        // dp[i][j] = LRS length considering first i chars and first j chars
        int[][] dp = new int[n + 1][n + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // If characters match AND positions are different
                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];
    }
    
    // Print the actual subsequence
    public String findLRS(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]);
                }
            }
        }
        
        // Backtrack to find the subsequence
        StringBuilder result = new StringBuilder();
        int i = n, j = n;
        
        while (i > 0 && j > 0) {
            if (dp[i][j] == dp[i - 1][j - 1] + 1 && 
                s.charAt(i - 1) == s.charAt(j - 1) && i != j) {
                result.insert(0, s.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        
        return result.toString();
    }
}

Complexity Analysis

  • Time Complexity: O(n²) - Filling the DP table
  • Space Complexity: O(n²) - For the DP table

Approach 3: Space Optimized DP

Intuition

Since we only need the previous row to compute the current row, we can reduce space to O(n).

java
public class Solution {
    public int longestRecurringSubseq(String s) {
        int n = s.length();
        
        int[] prev = new int[n + 1];
        int[] curr = new int[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) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }
        
        return prev[n];
    }
}

Complexity Analysis

  • Time Complexity: O(n²)
  • Space Complexity: O(n) - Only two rows needed

Key Takeaways

  1. This is a variation of LCS - finding LCS of string with itself
  2. The key constraint: same position cannot be used (i != j)
  3. The DP recurrence is similar to LCS but with position check
  4. Backtracking can be used to reconstruct the actual subsequence
  5. Space can be optimized from O(n²) to O(n) using rolling arrays
  6. Understanding LCS thoroughly makes this problem straightforward
Previous
Write a program to find the longest Palindrome in a string - Longest palindromic Substring
Next
Print all Subsequences of a string