Longest Repeating Subsequence
Explore how to identify the longest repeating subsequence in a string where repeated characters have distinct indexes. Understand the naive recursive solution and improve it with dynamic programming methods such as memoization and tabulation. This lesson helps you optimize time and space complexity while solving substring and subsequence problems.
Statement
Given a string, you have to find the length of the longest subsequence that occurs at least twice and respects this constraint: the characters that are re-used in each subsequence should have distinct indexes.
Note: A subsequence is part of an array whose elements are not necessarily contiguous. For example, given an array “abcde”, both “abcd” and “abe” are subsequences of the original array.
For example, let’s say you have to find the longest repeating subsequence from the string “aaaaba”. In this string, the longest repeating subsequence will be of length because the subsequence “aaaa” occurs twice.
Subsequence 1 = “aaaa” (indexes: 0, 1, 2, 3)
Subsequence 2 = “aaaa” (indexes: 1, 2, 3, 5)
Observing both subsequences, we note that the “a”'s at indexes , , and occur in both subsequences. However, we must understand that although they are repeating, the placement of these “a”'s is different in each subsequence. In the first subsequence, the “a” at index in the original string is placed at index , while in the second subsequence, it is placed at the index.
Constraints: