A13365 | Cow and Message

Bessie the cow has just intercepted a text that Farmer John sent to Burger Queen! However, Bessie is sure that there is a secret message hidden inside.

The text is a string $s$ of lowercase Latin letters. She considers a string $t$ as hidden in string $s$ if $t$ exists as a subsequence of $s$ whose indices form an arithmetic progression. For example, the string aab is hidden in string aaabb because it occurs at indices $1$ , $3$ , and $5$ , which form an arithmetic progression with a common difference of $2$ . Bessie thinks that any hidden string that occurs the most times is the secret message. Two occurrences of a subsequence of $S$ are distinct if the sets of indices are different. Help her find the number of occurrences of the secret message!

For example, in the string aaabb, a is hidden $3$ times, b is hidden $2$ times, ab is hidden $6$ times, aa is hidden $3$ times, bb is hidden $1$ time, aab is hidden $2$ times, aaa is hidden $1$ time, abb is hidden $1$ time, aaab is hidden $1$ time, aabb is hidden $1$ time, and aaabb is hidden $1$ time. The number of occurrences of the secret message is $6$ .

The first line contains a string $s$ of lowercase Latin letters ( $1 \le |s| \le 10^5$ ) — the text that Bessie intercepted.

Output a single integer — the number of occurrences of the secret message.