Longest Repeated Subsequence

Difficulty Level Medium
Frequently asked in Amazon Arcesium Avalara ByteDance Capital One Facebook MetLife
Binary Search Dynamic Programming Hash StringViews 2346

The problem “Longest Repeated Subsequence” states that you are given a string as an input. Find out the longest repeated subsequence, that is the subsequence that exists twice in the string.

Example

Longest Repeated Subsequence

aeafbdfdg
3 (afd)

Approach

The problem asks us to find out the longest repeated subsequence in the string. To recall, a subsequence is a string you are left with if you delete some of the characters from the string. So, a naive approach could be the generation of all subsequences. After the generation of the subsequence, we start checking whether any of the subsequences satisfy our requirement or not. But the generation of a subsequence is a time-consuming process. Thus we need to think of any other approach instead of generating the subsequences.

The other thing we can do is use dynamic programming. The problem is a slight variation over the Longest Common Subsequence. There are two changes. First, instead of two strings, we are operating on a single string. And the other thing is also related to the first fact. Since we are operating on a single string and want that the subsequence should be repeated. We require to select the characters which exclusively independent in both of the subsequence that is the index of characters should be different. So more formally speaking we will be calling the same function to find the longest common subsequence but instead of passing the second string. We pass the same string as the first and second argument with a condition that the index for the same characters should be different.

C++ code to find Longest Repeated Subsequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  string s = "aeafbdfdg";
    int n = s.length();
  int dp[n][n];memset(dp, 0, sizeof dp);
  for (int i=0;i<n;i++){
    for (int j=0;j<n;j++){
      if (s[i]==s[j] && i != j) 
        dp[i][j] = 1 + ((i>0 && j>0) ? dp[i-1][j-1] : 0);
      else
        dp[i][j] = max(((j>0) ? dp[i][j-1] : 0), ((i>0) ? dp[i-1][j] : 0));
    }
  }
    cout<<dp[n-1][n-1];
}
3

Java code to find Longest Repeated Subsequence

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    String s = "aeafbdfdg";
      int n = s.length();
    int dp[][] = new int[n+1][n+1]; 
    for (int i=0; i<=n; i++) 
      for (int j=0; j<=n; j++) 
        dp[i][j] = 0;
    for (int i=0;i<n;i++){
      for (int j=0;j<n;j++){
        if (s.charAt(i)==s.charAt(j) && i != j) 
          dp[i][j] = 1 + ((i>0 && j>0) ? dp[i-1][j-1] : 0);
        else
          dp[i][j] = Math.max(((j>0) ? dp[i][j-1] : 0), ((i>0) ? dp[i-1][j] : 0));
      }
    }
    System.out.print(dp[n-1][n-1]);
  }
}
3

Complexity Analysis

Time Complexity

O(N^2), because this approach is the same as that of the Longest Common Subsequence problem. Thus the time complexity is also similar to that.

Space Complexity

O(N^2), because we have to create a 2D DP table. Thus the space complexity is also polynomial.

Translate »