1307CUnreviewed1500GPT-5.4 (high)

Cow and Message

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

brute force dp math strings

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Start by ignoring long strings. How many times can a hidden string of length $1$ occur? What about length $2$ ? For length $2$ , notice that any pair of indices forms an arithmetic progression.

Now look at a hidden string $t$ of length at least $3$ . If you know the first two chosen indices $i_1, i_2$ , what is the common difference $d$ ? And once $d$ is fixed, how many choices are left for the remaining indices?

That means every occurrence of a string $t=t_1t_2\dots t_k$ with $k\ge 3$ is uniquely determined by an occurrence of just its prefix $t_1t_2$ . So the number of occurrences of any longer string is at most the number of occurrences of some length- $2$ string.

So the answer is simply

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

where $\text{pairs}[a][b]$ is the number of pairs $(i,j)$ with $i<j$ , $s_i=a$ , $s_j=b$ .

Count $\text{pairs}[a][b]$ in one left-to-right pass. Maintain $\text{cnt}[a] =$ how many times letter $a$ has appeared so far. When you read current letter $b$ , every previous $a$ creates a new subsequence $ab$ , so do

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

Then increment $\text{cnt}[b]$ . Use long long, because the answer can be about $\binom{10^5}{2}$ .

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:

Every length- $1$ hidden string is counted by $\text{cnt}$ .
Every length- $2$ hidden string is counted by $\text{pairs}$ .
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.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    string s;
    cin >> s;

    ll cnt[26] = {};
    ll pairs[26][26] = {};

    ll ans = 0;

    for (char ch : s) {
        int c = ch - 'a';

        for (int a = 0; a < 26; ++a) {
            pairs[a][c] += cnt[a];
        }

        cnt[c]++;
        ans = max(ans, cnt[c]);
    }

    for (int a = 0; a < 26; ++a) {
        for (int b = 0; b < 26; ++b) {
            ans = max(ans, pairs[a][b]);
        }
    }

    cout << ans << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    string s;
    cin >> s;

    ll cnt[26] = {};
    ll pairs[26][26] = {};

    ll ans = 0;

    for (char ch : s) {
        int c = ch - 'a';

        for (int a = 0; a < 26; ++a) {
            pairs[a][c] += cnt[a];
        }

        cnt[c]++;
        ans = max(ans, cnt[c]);
    }

    for (int a = 0; a < 26; ++a) {
        for (int b = 0; b < 26; ++b) {
            ans = max(ans, pairs[a][b]);
        }
    }

    cout << ans << '\n';
    return 0;
}

View on Codeforces Back to the list

Cow and Message

Progressive nudges

Full explanation

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

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

Observation 3: count all ordered pairs in one pass

Why this is correct

Complexity

Generated C++

Cow and Message

Progressive nudges

Full explanation

Observation 1: length 111 and 222 are easy

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

Observation 3: count all ordered pairs in one pass

Why this is correct

Complexity

Generated C++

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