Longest Repeating Subsequence
Last Updated : 23 Jul, 2025
Given a string s, the task is to find the length of the longest repeating subsequence, such that the two subsequences don't have the same string character at the same position, i.e. any ith character in the two subsequences shouldn't have the same index in the original string.
Examples:
Input: s= "abc"
Output: 0
Explanation: There is no repeating subsequence
Input: s= "aab"
Output: 1
Explanation: The two subsequence are 'a'(0th index) and 'a'(1th index). Note that 'b' cannot be considered as part of subsequence as it would be at same index in both.
Using Recursion - O(2^n) time and O(n) space
This problem is a variation of the longest common subsequence (LCS) problem. The idea is to treat the given string as two separate strings and find the LCS between them. However, to ensure that the subsequences are not overlapping, we add the condition that no character in the subsequences should come from the same index in the original string. This means that when comparing two characters from the two strings, they must match, and their indices must be different. By leveraging this condition, we can adapt the LCS approach to solve for the longest repeating subsequence.
The idea is to compare the characters at index i and j of s and the indices i and j. Two cases arise:
1. If the characters of the string match (s[i-1] == s[j-1]) and their indices are different (i != j), then make a recursive call for the remaining string (i-1 and j-1) and add 1 to the result.
- longestRepeatingSubsequence(i, j, s) = 1 + longestRepeatingSubsequence(i-1, j-1, s)
2. If the characters do not match or the indices are the same, make two recursive calls:
- longestRepeatingSubsequence(i, j, str) = max(longestRepeatingSubsequence(i-1, j, str), longestRepeatingSubsequence(i, j-1, str))
Base Case:
- If either of the strings becomes empty (i == 0 or j == 0), return 0.
C++ // C++ program to find longest // repeating subsequence using recursion #include <bits/stdc++.h> using namespace std; int findLongestRepeatingSubsequence(int i, int j, string &s) { // base case if (i == 0 || j == 0) return 0; // If characters match and their // indices are different if (s[i - 1] == s[j - 1] && i != j) { return 1 + findLongestRepeatingSubsequence(i - 1, j - 1, s); } // Else make two recursive calls. return max(findLongestRepeatingSubsequence(i - 1, j, s), findLongestRepeatingSubsequence(i, j - 1, s)); } int longestRepeatingSubsequence(string s) { int n = s.length(); return findLongestRepeatingSubsequence(n, n, s); } int main() { string s = "AABEBCDD"; int res = longestRepeatingSubsequence(s); cout << res; return 0; } // Java program to find longest // repeating subsequence using recursion class GfG { static int findLongestRepeatingSubsequence(int i, int j, String s) { // base case if (i == 0 || j == 0) return 0; // If characters match and their // indices are different if (s.charAt(i - 1) == s.charAt(j - 1) && i != j) { return 1 + findLongestRepeatingSubsequence(i - 1, j - 1, s); } // Else make two recursive calls. return Math.max( findLongestRepeatingSubsequence(i - 1, j, s), findLongestRepeatingSubsequence(i, j - 1, s)); } static int longestRepeatingSubsequence(String s) { int n = s.length(); return findLongestRepeatingSubsequence(n, n, s); } public static void main(String[] args) { String s = "AABEBCDD"; int res = longestRepeatingSubsequence(s); System.out.println(res); } } # Python program to find longest # repeating subsequence using recursion def findLongestRepeatingSubsequence(i, j, s): # base case if i == 0 or j == 0: return 0 # If characters match and their # indices are different if s[i - 1] == s[j - 1] and i != j: return 1 + findLongestRepeatingSubsequence(i - 1, j - 1, s) # Else make two recursive calls. return max(findLongestRepeatingSubsequence(i - 1, j, s), findLongestRepeatingSubsequence(i, j - 1, s)) def longestRepeatingSubsequence(s): n = len(s) return findLongestRepeatingSubsequence(n, n, s) if __name__ == "__main__": s = "AABEBCDD" res = longestRepeatingSubsequence(s) print(res)
// C# program to find longest // repeating subsequence using recursion using System; class GfG { static int findLongestRepeatingSubsequence(int i, int j, string s) { // base case if (i == 0 || j == 0) return 0; // If characters match and their // indices are different if (s[i - 1] == s[j - 1] && i != j) { return 1 + findLongestRepeatingSubsequence(i - 1, j - 1, s); } // Else make two recursive calls. return Math.Max( findLongestRepeatingSubsequence(i - 1, j, s), findLongestRepeatingSubsequence(i, j - 1, s)); } static int longestRepeatingSubsequence(string s) { int n = s.Length; return findLongestRepeatingSubsequence(n, n, s); } static void Main(string[] args) { string s = "AABEBCDD"; int res = longestRepeatingSubsequence(s); Console.WriteLine(res); } } // JavaScript program to find longest // repeating subsequence using recursion function findLongestRepeatingSubsequence(i, j, s) { // base case if (i === 0 || j === 0) return 0; // If characters match and their // indices are different if (s[i - 1] === s[j - 1] && i !== j) { return 1 + findLongestRepeatingSubsequence(i - 1, j - 1, s); } // Else make two recursive calls. return Math.max( findLongestRepeatingSubsequence(i - 1, j, s), findLongestRepeatingSubsequence(i, j - 1, s)); } function longestRepeatingSubsequence(s) { const n = s.length; return findLongestRepeatingSubsequence(n, n, s); } const s = "AABEBCDD"; const res = longestRepeatingSubsequence(s); console.log(res); Using Top-Down DP (Memoization) – O(n^2) Time and O(n^2) Space
If we notice carefully, we can observe that the above recursive solution holds the following two properties of Dynamic Programming:
1. Optimal Substructure: The maximum length of repeating subsequence originating from i, j, i.e., longestRepeatingSubsequence(i, j), depends on the optimal solution of longestRepeatingSubsequence(i-1, j-1) if characters match and indices don't match. Otherwise, it depends on the maximum of longestRepeatingSubsequence(i-1, j) and longestRepeatingSubsequence(i, j-1).
2. Overlapping Subproblems: While applying a recursive approach in this problem, we notice that certain subproblems are computed multiple times.
- There are two parameters, i and j that changes in the recursive solution. So we create a 2D array of size n*n for memoization.
- We initialize this array as -1 to indicate nothing is computed initially.
- Now we modify our recursive solution to first check if the value is -1, then only make recursive calls. This way, we avoid re-computations of the same subproblems.
C++ // C++ program to find longest // repeating subsequence using memoization #include <bits/stdc++.h> using namespace std; int findLongestRepeatingSubsequence(int i, int j, string &s, vector<vector<int>> &memo) { // base case if (i == 0 || j == 0) return 0; // If value is computed, return it. if (memo[i - 1][j - 1] != -1) return memo[i - 1][j - 1]; // If characters match and their // indices are different if (s[i - 1] == s[j - 1] && i != j) { return memo[i - 1][j - 1] = 1 + findLongestRepeatingSubsequence(i - 1, j - 1, s, memo); } // Else make two recursive calls. return memo[i - 1][j - 1] = max(findLongestRepeatingSubsequence(i - 1, j, s, memo), findLongestRepeatingSubsequence(i, j - 1, s, memo)); } int longestRepeatingSubsequence(string s) { int n = s.length(); vector<vector<int>> memo(n, vector<int>(n, -1)); return findLongestRepeatingSubsequence(n, n, s, memo); } int main() { string s = "AABEBCDD"; int res = longestRepeatingSubsequence(s); cout << res; return 0; } // Java program to find longest // repeating subsequence using memoization class GfG { static int findLongestRepeatingSubsequence(int i, int j, String s, int[][] memo) { // base case if (i == 0 || j == 0) return 0; // If value is computed, return it. if (memo[i - 1][j - 1] != -1) return memo[i - 1][j - 1]; // If characters match and their // indices are different if (s.charAt(i - 1) == s.charAt(j - 1) && i != j) { return memo[i - 1][j - 1] = 1 + findLongestRepeatingSubsequence( i - 1, j - 1, s, memo); } // Else make two recursive calls. return memo[i - 1][j - 1] = Math.max(findLongestRepeatingSubsequence( i - 1, j, s, memo), findLongestRepeatingSubsequence( i, j - 1, s, memo)); } static int longestRepeatingSubsequence(String s) { int n = s.length(); int[][] memo = new int[n][n]; for (int[] row : memo) { java.util.Arrays.fill(row, -1); } return findLongestRepeatingSubsequence(n, n, s, memo); } public static void main(String[] args) { String s = "AABEBCDD"; int res = longestRepeatingSubsequence(s); System.out.println(res); } } # Python program to find longest # repeating subsequence using memoization def findLongestRepeatingSubsequence(i, j, s, memo): # base case if i == 0 or j == 0: return 0 # If value is computed, return it. if memo[i - 1][j - 1] != -1: return memo[i - 1][j - 1] # If characters match and their # indices are different if s[i - 1] == s[j - 1] and i != j: memo[i - 1][j - 1] = 1 + \ findLongestRepeatingSubsequence(i - 1, j - 1, s, memo) return memo[i - 1][j - 1] # Else make two recursive calls. memo[i - 1][j - 1] = max(findLongestRepeatingSubsequence(i - 1, j, s, memo), findLongestRepeatingSubsequence(i, j - 1, s, memo)) return memo[i - 1][j - 1] def longestRepeatingSubsequence(s): n = len(s) memo = [[-1 for _ in range(n)] for _ in range(n)] return findLongestRepeatingSubsequence(n, n, s, memo) if __name__ == "__main__": s = "AABEBCDD" res = longestRepeatingSubsequence(s) print(res)
// C# program to find longest // repeating subsequence using memoization using System; class GfG { static int findLongestRepeatingSubsequence(int i, int j, string s, int[, ] memo) { // base case if (i == 0 || j == 0) return 0; // If value is computed, return it. if (memo[i - 1, j - 1] != -1) return memo[i - 1, j - 1]; // If characters match and their // indices are different if (s[i - 1] == s[j - 1] && i != j) { memo[i - 1, j - 1] = 1 + findLongestRepeatingSubsequence( i - 1, j - 1, s, memo); return memo[i - 1, j - 1]; } // Else make two recursive calls. memo[i - 1, j - 1] = Math.Max(findLongestRepeatingSubsequence( i - 1, j, s, memo), findLongestRepeatingSubsequence( i, j - 1, s, memo)); return memo[i - 1, j - 1]; } static int longestRepeatingSubsequence(string s) { int n = s.Length; int[, ] memo = new int[n, n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { memo[i, j] = -1; } } return findLongestRepeatingSubsequence(n, n, s, memo); } static void Main(string[] args) { string s = "AABEBCDD"; int res = longestRepeatingSubsequence(s); Console.WriteLine(res); } } // JavaScript program to find longest // repeating subsequence using memoization function findLongestRepeatingSubsequence(i, j, s, memo) { // base case if (i === 0 || j === 0) return 0; // If value is computed, return it. if (memo[i - 1][j - 1] !== -1) return memo[i - 1][j - 1]; // If characters match and their // indices are different if (s[i - 1] === s[j - 1] && i !== j) { return memo[i - 1][j - 1] = 1 + findLongestRepeatingSubsequence( i - 1, j - 1, s, memo); } // Else make two recursive calls. return memo[i - 1][j - 1] = Math.max(findLongestRepeatingSubsequence( i - 1, j, s, memo), findLongestRepeatingSubsequence( i, j - 1, s, memo)); } function longestRepeatingSubsequence(str) { const n = s.length; const memo = Array.from({length : n}, () => Array(n).fill(-1)); return findLongestRepeatingSubsequence(n, n, s, memo); } const s = "AABEBCDD"; const res = longestRepeatingSubsequence(s); console.log(res); Using Bottom-Up DP (Tabulation) - O(n^2) Time and O(n^2) Space
The approach is similar to the previous one. just instead of breaking down the problem recursively, we iteratively build up the solution by calculating in bottom-up manner. The idea is to create a 2-D array. Then fill the values using dp[i][j] = 1 + dp[i-1][j-1] if characters match and indices don't match. Otherwise, set dp[i][j] = max(dp[i-1][j], dp[i], [j-1]).
C++ // C++ program to find longest // repeating subsequence using tabulation #include <iostream> #include <vector> using namespace std; int longestRepeatingSubsequence(string& s) { int n = s.length(); vector<vector<int>> dp(n+1, vector<int>(n+1, 0)); for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { // If char match and indices // are different if (s[i-1]==s[j-1] && i!=j) { dp[i][j] = 1 + dp[i-1][j-1]; } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } return dp[n][n]; } int main() { string s = "AABEBCDD"; int res = longestRepeatingSubsequence(s); cout << res; return 0; } // Java program to find longest // repeating subsequence using tabulation class GfG { static 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 char match and indices // are different 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]; } public static void main(String[] args) { String s = "AABEBCDD"; int res = longestRepeatingSubsequence(s); System.out.println(res); } } # Python program to find longest # repeating subsequence using tabulation def longestRepeatingSubsequence(s): n = len(s) dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, n + 1): # If char match and indices # are different if s[i - 1] == s[j - 1] and i != j: dp[i][j] = 1 + dp[i - 1][j - 1] else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[n][n] if __name__ == "__main__": s = "AABEBCDD" res = longestRepeatingSubsequence(s) print(res)
// C# program to find longest // repeating subsequence using tabulation using System; class GfG { static 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 char match and indices // are different if (s[i - 1] == s[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]; } static void Main(string[] args) { string s = "AABEBCDD"; int res = longestRepeatingSubsequence(s); Console.WriteLine(res); } } // JavaScript program to find longest // repeating subsequence using tabulation function longestRepeatingSubsequence(s) { const n = s.length; const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0)); for (let i = 1; i <= n; i++) { for (let j = 1; j <= n; j++) { // If char match and indices // are different if (s[i - 1] === s[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]; } const s = "AABEBCDD"; const res = longestRepeatingSubsequence(s); console.log(res); Using Space Optimized DP - O(n^2) Time and O(n) Space
The idea is store the values for the previous row only. We can observe that for a given (i, j) its value is only dependent on (i-1, j-1) or (i-1, j) and (i, j-1).
C++ // C++ program to find longest // repeating subsequence // using space optimization #include <bits/stdc++.h> using namespace std; int longestRepeatingSubsequence(string& s) { int n = s.length(); // Create a 1D array for the current row vector<int> curr(n + 1, 0); // Variable to store dp[i-1][j-1] for each (i, j) // This helps to track the diagonal value from the previous iteration int match = 0; for (int i = 1; i <= n; i++) { // Reset match to 0 for the new row match = 0; for (int j = 1; j <= n; j++) { // Store the current cell value before updating int tmp = curr[j]; // If characters match and indices are different if (s[i - 1] == s[j - 1] && i != j) { // Add 1 to the diagonal value curr[j] = 1 + match; } else { // Take the maximum value between left and top cells curr[j] = max(curr[j], curr[j - 1]); } // Update match to the previous cell value match = tmp; } } return curr[n]; } int main() { string s = "AABEBCDD"; int res = longestRepeatingSubsequence(s); cout << res; return 0; } // Java program to find the longest // repeating subsequence using space optimization class GfG { static int longestRepeatingSubsequence(String s) { // Get the length of the input string int n = s.length(); // Create a 1D array to store the current row's // values int[] curr = new int[n + 1]; // Variable to store the value of dp[i-1][j-1] // (diagonal element) int match; // Iterate over all characters of the string for row // index for (int i = 1; i <= n; i++) { // Reset match for each new row match = 0; // Iterate over all characters of the string for // column index for (int j = 1; j <= n; j++) { // Temporarily store the current cell value // before updating it int tmp = curr[j]; // If characters match and indices are // different, update with diagonal value + 1 if (s.charAt(i - 1) == s.charAt(j - 1) && i != j) { curr[j] = 1 + match; } else { // Otherwise, take the maximum of the // left and top cells curr[j] = Math.max(curr[j], curr[j - 1]); } // Update match to the previously stored // value of curr[j] match = tmp; } } // Return the value in the last cell, which contains // the length of the longest repeating subsequence return curr[n]; } public static void main(String[] args) { String s = "AABEBCDD"; int res = longestRepeatingSubsequence(s); System.out.println(res); } } # Python program to find the longest # repeating subsequence using space optimization def longestRepeatingSubsequence(s): # Get the length of the input string n = len(s) # Create a 1D array to store the current row's values curr = [0] * (n + 1) # Variable to store the value of dp[i-1][j-1] (diagonal element) match = 0 # Iterate over all characters of the string for row index for i in range(1, n + 1): # Reset match for each new row match = 0 # Iterate over all characters of the string for column index for j in range(1, n + 1): # Temporarily store the current cell value before updating it tmp = curr[j] # If characters match and indices are different, # update with diagonal value + 1 if s[i - 1] == s[j - 1] and i != j: curr[j] = 1 + match else: # Otherwise, take the maximum of the left and top cells curr[j] = max(curr[j], curr[j - 1]) # Update match to the previously stored value of curr[j] match = tmp # Return the value in the last cell, which contains the length of # the longest repeating subsequence return curr[n] if __name__ == "__main__": s = "AABEBCDD" res = longestRepeatingSubsequence(s) print(res)
// C# program to find the longest // repeating subsequence using space optimization using System; class GfG { static int longestRepeatingSubsequence(string s) { // Get the length of the input string int n = s.Length; // Create a 1D array to store the current row's // values int[] curr = new int[n + 1]; // Variable to store the value of dp[i-1][j-1] // (diagonal element) int match = 0; // Iterate over all characters of the string for row // index for (int i = 1; i <= n; i++) { // Reset match for each new row match = 0; // Iterate over all characters of the string for // column index for (int j = 1; j <= n; j++) { // Temporarily store the current cell value // before updating it int tmp = curr[j]; // If characters match and indices are // different, update with diagonal value + 1 if (s[i - 1] == s[j - 1] && i != j) { curr[j] = 1 + match; } else { // Otherwise, take the maximum of the // left and top cells curr[j] = Math.Max(curr[j], curr[j - 1]); } // Update match to the previously stored // value of curr[j] match = tmp; } } // Return the value in the last cell, which contains // the length of the longest repeating subsequence return curr[n]; } static void Main(string[] args) { string s = "AABEBCDD"; int res = longestRepeatingSubsequence(s); Console.WriteLine(res); } } // JavaScript program to find the longest // repeating subsequence using space optimization function longestRepeatingSubsequence(s) { // Get the length of the input string const n = s.length; // Create an array to store the current row's values const curr = new Array(n + 1).fill(0); // Variable to store the value of dp[i-1][j-1] (diagonal // element) let match = 0; // Iterate over all characters of the string for row // index for (let i = 1; i <= n; i++) { // Reset match for each new row match = 0; // Iterate over all characters of the string for // column index for (let j = 1; j <= n; j++) { // Temporarily store the current cell value // before updating it const tmp = curr[j]; // If characters match and indices are // different, update with diagonal value + 1 if (s[i - 1] === s[j - 1] && i !== j) { curr[j] = 1 + match; } else { // Otherwise, take the maximum of the left // and top cells curr[j] = Math.max(curr[j], curr[j - 1]); } // Update match to the previously stored value // of curr[j] match = tmp; } } // Return the value in the last cell, which contains the // length of the longest repeating subsequence return curr[n]; } const s = "AABEBCDD"; const res = longestRepeatingSubsequence(s); console.log(res);
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile