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 44 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 11, 22, and 33 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 11 in the original string is placed at index 11, while in the second subsequence, it is placed at the 0th0th index.

Constraints:

  • 00 \leq str.length 2000\leq 2000

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.