Longest Repeating Subsequence
Given string str, 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.
Example 1:
Input: str = "axxxy"
Output: 2
Explanation: The longest repeating subsequence
is "xx".Example 2:
Input: str = "aab"
output: 1
Explanation: The longest repeating subsequences
is "a".Your Task:
You don’t need to read or print anything. Your task is to complete the function LongestRepeatingSubsequence() which takes str as input parameter and returns the length of the longest repeating subsequence.
Expected Time Complexity: O(n2)
Expected Space Complexity: O(n2)
Constraints:
1 <= |str| <= 500
Before we look into the solution, let us understand the problem statement.
We are given an input string, and we have to find the longest repeating subsequence. A repeating subsequence is a subsequence whose characters will be repeating. Okay, this is confusing, let us take an example.
If we look at one of the given examples,
Input: str = "axxxy"
Output: 2
Explanation: The longest repeating subsequence
is "xx".How come the answer is 2 instead of 1? As we have 3 “x”, we cannot be creating a repeating subsequence. Isn’t it?
If we observe both the subsequence, we see that the “x” at index 2 is repeated twice. But we need to understand that though index 2 is repeating, the placement of that “x” is at different positions in the subsequence. In the first subsequence, “x” of index 2 is placed at index 1 of the subsequence, while in the second subsequence, “x” of index 2 is placed at the index 0 of the subsequence.
Now let us move to the solution.
The question is a variation of the Longest common subsequence with a minor variation. In the longest common subsequence, we were given two input strings and we were supposed to find subsequence which is common in both the input strings. In the given problem statement, we are given one input string, we will repeat the input string once, hence we will get two input strings. From these two input strings, we will find the common subsequence.
Wait! if we try looking for the longest common subsequence from two repeated strings, the answer will be the length of the string itself.
One modification that needs to be made is to ensure that the matching characters do not have matching indexes too. That means, if string1[i] == string2[j] then i and j should have different values.
Let us look into the code snippet.
class LongestRepeatingSubsequenceFinder:
def LongestRepeatingSubsequence(self, str):
memo = [[0 for j in range(len(str)+1)]for i in range(len(str)+1)]
for i in range(1, len(memo)):
for j in range(1,len(memo[0])):
if str[i-1] == str[j-1] and i != j:
memo[i][j] = memo[i-1][j-1]+1
else:
memo[i][j] = max(memo[i][j-1],memo[i-1][j])
return memo[-1][-1]Complexity analysis.
Time Complexity
We are traversing through a 2D array of size N², hence the time complexity is O(N²), where N is the size of the string.
Space Complexity.
We are creating a 2D array of size N², hence the space complexity is O(N²), where N is the size of the string.
Link to Aditya Verma’s video
