Cow and Message

The whole trick is realizing that long hidden strings are mostly bluffing.

Observation 1: length $1$ and $2$ are easy

Let $s$ be the given string.

• A hidden string of length $1$ is just a single character. Its number of occurrences is the frequency of that character.
• A hidden string of length $2$ is any ordered pair of characters taken from positions $i<j$.

Why is length $2$ this easy? Because any two indices form an arithmetic progression. No extra restriction. Zero drama.

So if we define:

$$\text{cnt}[c] = \#\{i : s_i = c\}$$

and

$$\text{pairs}[a][b] = \#\{(i,j) : i<j,\ s_i=a,\ s_j=b\},$$

then every hidden string of length $1$ or $2$ is handled by these values.

Observation 2: any occurrence of a longer string is determined by its first two indices

Now take some hidden string

$$t = t_1 t_2 \dots t_k, \quad k \ge 3.$$

An occurrence of $t$ uses indices

$$i_1 < i_2 < \dots < i_k$$

that form an arithmetic progression. So there exists a common difference $d$ such that

$$i_j = i_1 + (j-1)d.$$

The moment you know $i_1$ and $i_2$, you know

$$d = i_2 - i_1,$$

and therefore all remaining indices are forced:

$$i_3 = i_1 + 2d,\ i_4 = i_1 + 3d,\ \dots$$

So for a fixed string $t$, each occurrence is uniquely determined by the first two chosen positions.

That gives an injection:

• every occurrence of $t$ maps to an occurrence of the length-$2$ string $t_1t_2$.

Therefore,

$$\#\text{occurrences of } t \le \#\text{occurrences of } t_1t_2.$$

This is the key punchline:

No hidden string of length at least $3$ can occur more times than some hidden string of length $2$.

So the answer is simply

$$\max\left(\max_c \text{cnt}[c],\ \max_{a,b} \text{pairs}[a][b]\right).$$

That’s the entire problem. Yep, really.

Observation 3: count all ordered pairs in one pass

We need to compute $\text{pairs}[a][b]$ efficiently.

Process the string from left to right. Suppose the current character is $b$.

For every letter $a$:

• each previous occurrence of $a$ can pair with this $b$,
• so we add the number of previous $a$'s to $\text{pairs}[a][b]$.

If cnt[a] stores how many times letter $a$ has already appeared, then when reading character $b$:

$$\text{pairs}[a][b] += \text{cnt}[a] \quad \forall a \in [0,25].$$

Then we do

$$\text{cnt}[b]++.$$

Since there are only $26$ lowercase letters, this is

$$O(26n),$$

which is basically linear.

Why this is correct

We’ve already shown two facts:

1. Every length-$1$ hidden string is counted by $\text{cnt}$.
2. Every length-$2$ hidden string is counted by $\text{pairs}$.
3. Every hidden string of length $\ge 3$ has at most as many occurrences as its first two characters.

So taking the maximum over all single letters and all ordered pairs covers all possible hidden strings.

No fancy DP table over positions, no arithmetic progression enumeration, no nonsense. Just count letters and ordered pairs.

Complexity

• Time: $O(26n + 26^2) = O(n)$
• Memory: $O(26^2)$

Use long long, because the number of pairs can be as large as

$$\binom{10^5}{2} \approx 5 \cdot 10^9.$$

That does not fit in int. Don’t throw the submission away over something that dumb.