Home » Interview coding problems/challenges

# Longest Repeating Subsequence

**Longest Repeating Subsequence**: Here, we are going to learn about the solution of **Longest Repeating Subsequence** – which is an interview coding questions featured in any rounds of top companies.

Submitted by Radib Kar, on February 21, 2020

**Description:**

This question has been featured in interview rounds of Amazon.

**Problem statement:**

Given string * str*, find the

**length of the longest repeating subsequence**such that the two subsequences don't have the same character in the same position, i.e., any

**i**character in the two sub-sequences shouldn't have the same index in its original string.

^{th}Let the string be, Str="includehelpisbest" Output will be: Longest repeating sub-sequence length is 3 The longest repeating sub-sequence is:"ies"

The output is given above where the repeating sub-sequences are in two different colours. One more repeating subs-sequence can be,

**Solution Approach:**

The problem can be solved in similar way as longest Common subsequence problem, where input to **LCS()** would be String str both the case. That is

LRS(str) = LCS(str,str) which some constraints

Let's discuss the recursive approach first.

Let,

l = Length of the string,str f(l,l) = Longest repeating subsequence length for string length l

Now,

Think of the following example,

Say the string is: **x _{1}x_{2}...x_{l}**

Say,

**x _{i}==x_{j}** and

**i≠j**(this is the constraint what we discussed above)

Then obviously we need to find LCS for the remaining part of string **(x _{1}x_{2}...x_{i-1}, x_{1}x_{2}...x_{j-1})** and then add 1 for this valid character match (repeating character match),

Else

Maximum of two case,

- LCS of the string leaving character
**x**and string_{i},x_{1}x_{2}...x_{i-1}**x**._{1}x_{2}...x_{j} - LCS of the string
**x**and second string leaving character_{l1}, x_{1}x_{2}...x_{i}**x**_{j},x_{1}x_{2}...x_{j-1}

Now, we need to recur down to 0. So,

Where base cases are,

f(0,i)=0 for 0≤i≤l f(i,0)=0 for 0≤i≤ l

If you generate this recursion tree, it will generate many overlapping sub-problems and thus, we need to reduce the re-computing. That's why we need to convert it into dynamic programming where we will store the output of the sub-problems and we will use it to compute bigger sub-problems.

**Converting to Dynamic programming:**

1) Initialize dp[l+1][l+1] to 0 2) Convert the base case of recursion: for i=0 to l dp[i][0]=0; for i=0 to l dp[0][i]=0; 3) Fill the DP table as per recursion. for i=1 to l //i be the subproblem length for first string of LCS for j=1 to l //j be the subproblem length for second string of LCS if(i≠j and str1[i-1]==str2[j-1]) //xi==xjand i≠j dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); end for end for 4) The final output will be dp[l][l]

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; void print(vector<int> a, int n) { for (int i = 0; i < n; i++) cout << a[i] << " "; cout << endl; } int max(int a, int b) { return (a > b) ? a : b; } int LRS(string str1, string str2) { int l = str1.length(); int dp[l + 1][l + 1]; //base case for (int i = 0; i <= l; i++) dp[i][0] = 0; for (int i = 0; i <= l; i++) dp[0][i] = 0; //fill up for (int i = 1; i <= l; i++) { for (int j = 1; j <= l; j++) { if (i != j && str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } return dp[l][l]; } int main() { string str; cout << "Enter the string:\n"; cin >> str; cout << "Longest repeating sub-sequence length: " << LRS(str, str) << endl; return 0; }

**Output**

Enter the string: includehelpisbest Longest repeating sub-sequence length: 3

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions