Introduction

We are given a string $S$ containing only the three characters A, B, and C, and need to count its nonempty substrings satisfying:

The numbers of occurrences of A, B, and C in the substring are pairwise distinct.

Let the three character counts in a substring be $a,b,c$. The validity condition is that $a,b,c$ are pairwise distinct:

Equivalently:

The string length satisfies:

So we cannot enumerate all substrings directly.

1. The Problem with Brute Force

The most direct idea is to enumerate every substring $[l,r]$, then use prefix sums to obtain its counts of A, B, and C in $O(1)$.

For example, precompute the following, where preA[i], preB[i], and preC[i] count the respective characters among the first i characters:

1
2
3

preA[i] = 前 i 个字符中 A 的出现次数
preB[i] = 前 i 个字符中 B 的出现次数
preC[i] = 前 i 个字符中 C 的出现次数

The three counts in substring $[l,r]$ are then:

We can then check whether $a,b,c$ are pairwise distinct.

However, the number of substrings is:

When $N=2\times 10^5$, this is on the order of $10^{10}$, so enumerating substrings in $O(N^2)$ is infeasible.

The key question is not how to find one substring’s character counts quickly, but:

How can we count substrings satisfying a particular relationship between their counts without enumerating the substrings?

2. Count the Invalid Substrings Instead

We need to count substrings satisfying:

Counting pairwise-distinct frequencies directly is awkward, so consider the complement.

An invalid substring satisfies at least one condition: $a=b$, or $b=c$, or $c=a$:

We can therefore start by counting:

• Substrings with equal numbers of A and B
• Substrings with equal numbers of B and C
• Substrings with equal numbers of C and A

Then subtract the number of invalid substrings from the total.

But these three sets overlap. If a substring satisfies:

it belongs to all three sets:

• $a=b$
• $b=c$
• $c=a$

In other words, it is counted three times.

As an invalid substring, however, it should be counted only once.

We will therefore need inclusion–exclusion to handle this overlap.

3. From $A=B$ to Equal Prefix Differences

First consider just one condition: a substring contains equal numbers of A and B.

Define the prefix difference:

If substring $[l,r]$ contains equal numbers of A and B, then:

Rearranging gives:

That is:

Therefore:

Substring $[l,r]$ contains equal numbers of A and B if and only if the difference $preA-preB$ is the same at prefix positions $r$ and $l-1$.

This changes the problem from enumerating substrings to counting how often the same prefix state occurs.

4. Counting Prefix States

If we scan the string from left to right while maintaining the current prefix difference $d$, then at each prefix position we only need to know:

How many earlier prefix positions also had a difference equal to the current $d$?

Suppose the current difference is $d$, and it has already occurred mp[d] times. Each of those earlier positions can pair with the current prefix position to form a substring with equal numbers of A and B.

The new contribution is therefore:

1
2

ans += mp[d];
mp[d]++;

Rather than enumerating every left endpoint, this uses mp[d] to count all eligible left endpoints at once.

Similarly:

• To count $a=b$, use the difference $preA-preB$
• To count $b=c$, use the difference $preB-preC$
• To count $c=a$, use the difference $preC-preA$

The corresponding code is:

1
2
3
4
5
6
7
8

int d1 = preA - preB;
tot2 += mpAB[d1]++;

int d2 = preB - preC;
tot2 += mpBC[d2]++;

int d3 = preC - preA;
tot2 += mpCA[d3]++;

Here, tot2 records the sum of the sizes of the three sets:

5. Why We Also Need to Count $A=B=C$

If we calculate only:

we count some substrings more than once.

A substring satisfying:

also satisfies all of the following:

It is therefore counted once in each of $cnt_{AB}$, $cnt_{BC}$, and $cnt_{CA}$, for a total of three times.

It should be counted only once as an invalid substring, so there are two extra counts.

Let $cnt_{ABC}$ be the number of substrings satisfying $a=b=c$. The number of invalid substrings is then:

The final answer is therefore:

Or:

In code:

1

cout << tot - tot2 + tot3 * 2;

Here:

• tot: the number of all nonempty substrings
• tot2: $cnt_{AB}+cnt_{BC}+cnt_{CA}$
• tot3: $cnt_{ABC}$

6. Counting $A=B=C$ with a Two-Dimensional State

Next, we need to count substrings satisfying:

This can be split into two conditions:

For each prefix state, we can therefore maintain two differences at once:

For substring $[l,r]$, if:

the substring between those prefix positions satisfies both:

and:

Hence:

We can therefore count using a two-dimensional state:

1

tot3 += mpABC[getKey(d1, d2)]++;

The differences used here are:

1
2

d1 = preA - preB;
d2 = preB - preC;

Whenever two prefix positions have exactly the same (d1,d2), the substring between them satisfies A=B=C.

7. Encoding a Two-Dimensional State as long long

In C++, unordered_map<pair<int,int>, long long> cannot be used directly with its default settings, because the standard library provides no default hash function for pair<int,int>.

We can instead encode the two-dimensional state manually as a long long.

The code is:

1
2
3
4
5

constexpr ll offset = 200005, base = 500005;

ll getKey(int x, int y) {
    return 1ll * (x + offset) * base + (y + offset);
}

The prefix differences stay within:

Since $N\le 2\times 10^5$, adding offset makes each difference nonnegative.

base must be larger than the maximum possible value of the second coordinate, so that distinct pairs cannot be encoded as the same key.

One way to understand this is:

Encode the two-dimensional coordinates $(x,y)$ as one integer, much like a positional numeral system.

That is:

As long as:

the encoding is unique.

8. Initialization

We must include the empty prefix, too.

For a substring $[1,r]$ starting at the $1$st character, the corresponding prefix endpoints are $0$ and $r$:

Initially, each zero-difference state must therefore have one occurrence:

1
2
3
4
5
6
7

void init() {
    mpAB[0] = 1;
    mpBC[0] = 1;
    mpCA[0] = 1;
    mpABC[getKey(0, 0)] = 1;
    tot = 1ll * n * (n + 1) / 2;
}

Here:

is the number of all nonempty substrings.

From the prefix perspective, there are $N+1$ prefix positions. Choosing any two distinct prefix positions determines a nonempty substring, so we can also write:

9. The Main Loop

While scanning the string, we only need the counts of A, B, and C in the current prefix; there is no need to store entire prefix arrays.

1
2
3
4
5
6
7
8
9
10

for (int i = 0; i < n; i++) {
    if (s[i] == 'A') {
        preA++;
    } else if (s[i] == 'B') {
        preB++;
    } else {
        preC++;
    }
    cnt();
}

After reading each character, update the current prefix counts, then count the new contributions whose right endpoint is the current position.

The cnt function is:

1
2
3
4
5
6
7
8
9

void cnt() {
    int d1 = preA - preB;
    tot2 += mpAB[d1]++;
    int d2 = preB - preC;
    tot2 += mpBC[d2]++;
    int d3 = preC - preA;
    tot2 += mpCA[d3]++;
    tot3 += mpABC[getKey(d1, d2)]++;
}

The central idea is:

Each earlier occurrence of the current state adds one valid pair ending at the current position.

10. Complete Code and Submission Record

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll offset = 200005, base = 500005;

int n, preA, preB, preC;
ll tot, tot2, tot3;
string s;
unordered_map<int, ll> mpAB, mpBC, mpCA;
unordered_map<ll, ll> mpABC;

ll getKey(int x, int y) {
    return 1ll * (x + offset) * base + (y + offset);
}

void init() {
    mpAB[0] = 1;
    mpBC[0] = 1;
    mpCA[0] = 1;
    mpABC[getKey(0, 0)] = 1;
    tot = 1ll * n * (n + 1) / 2;
}

void cnt() {
    int d1 = preA - preB;
    tot2 += mpAB[d1]++;
    int d2 = preB - preC;
    tot2 += mpBC[d2]++;
    int d3 = preC - preA;
    tot2 += mpCA[d3]++;
    tot3 += mpABC[getKey(d1, d2)]++;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s;
    init();

    for (int i = 0; i < n; i++) {
        if (s[i] == 'A') {
            preA++;
        } else if (s[i] == 'B') {
            preB++;
        } else {
            preC++;
        }
        cnt();
    }

    cout << tot - tot2 + tot3 * 2;
    return 0;
}

The submission record below shows that both the time and space performance are quite good.

And here are some notes I scribbled while working on the problem :)

11. Complexity Analysis

We scan the string once, performing a constant number of hash-table lookups and updates at each position, so the time complexity is:

At most $O(N)$ prefix states are stored in the hash tables, so the space complexity is:

In this problem:

so this complexity is sufficient to pass.

Closing Thoughts

The key to this problem is not prefix sums themselves, but turning relationships between character counts in a substring into equality between two prefix states.

A condition such as $a=b$ can be counted using one-dimensional prefix differences. A condition such as $a=b=c$, which requires two equalities to hold simultaneously, needs a two-dimensional prefix state.

Finally, inclusion–exclusion handles the repeated counts among the three sets of invalid substrings.

The overall approach is:

1. Use all substrings as the universal set
2. Count the invalid substrings in which at least two character counts are equal
3. Use prefix differences to count the three one-dimensional conditions
4. Use two-dimensional differences to count the overlap where all three counts are equal
5. Apply inclusion–exclusion to obtain the final answer

The useful lesson from problems like this is:

Prefix sums do more than answer interval-sum queries quickly. Equality between prefix states can also count intervals satisfying particular relationships.