Longest Repeating Subsequence

Given a string s, return the length of the longest subsequence that appears at least twice in s, using different indices for the repeated occurrences. Pattern focus: LCS Style DP. This is the classic self-LCS problem with the index inequality constraint i != j.

Input Format

s = input string

Output Format

length of the longest repeating subsequence

Constraints

  • 1 <= s.length <= 1000
  • s contains lowercase English letters.

Examples

Example 1:

Input:

s = "axxxy"

Output:

2

Explanation:

The repeating subsequence is xx.

Example 2:

Input:

s = "aab"

Output:

1

Explanation:

The repeating subsequence is a.

Loading...
Longest Repeating Subsequence - Dp Strings