Longest Repeating Subsequence

You are given a string S. Your task is to determine the length of the longest subsequence that appears at least twice in S without any overlap in the positions of the characters. In other words, find the maximum length L such that there exist two subsequences of S (not necessarily contiguous) which are identical, and for every position i the indices used in the two subsequences are different.

This problem can be solved using dynamic programming. One typical approach is to use a 2D DP array where dp[i][j] represents the length of the longest repeating subsequence in the prefixes ending at positions i and j of the string. Note that when S[i] is compared with S[j], they should be equal and the indices must not be the same.

The answer is the value in dp[n][n] where n is the length of the string.

inputFormat

Input is provided via standard input (stdin). The input consists of a single line containing the string S. The string S will have at most 1000 characters.

outputFormat

Output the length of the longest repeating subsequence as an integer to standard output (stdout).## sample

a

0