### PROBLEM LINK:

**Author:** Konstantin Sokol

**Tester:** Gerald Agapov

**Editorialist:** Tasnim Imran Sunny

### DIFFICULTY:

Simple

### PREREQUISITES:

Ad-Hoc, Map

### PROBLEM:

Given a string **S** which is consisted of characters ‘A’, ‘B’ or ‘C’. Find the number of substrings of **S** which have equal number of ‘A’s, ‘B’s and ‘C’s.

### EXPLANATION:

Let,

A_{i} = Number of ‘A’s in **S** between the indexes 1 and i (inclusive).

B_{i} = Number of ‘B’s in **S** between the indexes 1 and i (inclusive).

C_{i} = Number of ‘C’s in **S** between the indexes 1 and i (inclusive).

Let’s consider the substring **S _{j…i}** :

Number of ‘

**A**’-s in that substring =

**A**

_{i}- A_{j-1}Number of ‘

**B**’-s in that substring =

**B**

_{i}- B_{j-1}Number of ‘

**C**’-s in that substring =

**C**

_{i}- C_{j-1}So for that substring to be good:

**A _{i} - A_{j-1} = B_{i} - B_{j-1} = C_{i} - C_{j-1}**

Alternatively the following two conditions are enough for that substring to be good:

**A _{i} - B_{i} = A_{j-1} - B_{j-1}**

A_{i} - C_{i} = A_{j-1} - C_{j-1}

Go from left to right and for each index **i** find the number of valid good substrings which ends at **i**. The number of such substrings would be the number of indexes **k (k < i)** where **(A _{i} - B_{i}, A_{i} - C_{i} )= (A_{k} - B_{k}, A_{k} - C_{k} )**. That can be obtained if the pair

**(A**)for all

_{k}- B_{k}, A_{k}- C_{k}**k**are stored in a key-value storage where the key being the pair and value being the number indexes having that difference pair. If using C++, STL Map can be used.

The author did not use a map, instead he computed all the difference pairs and then sorted those and then find the number of equal pairs.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.