**PROBLEM LINK**:

Practice

Contest, div. 1

Contest, div. 2

**Author:** Jas Mehta

**Tester:** Zhong Ziqian

**Editorialist:** Oleksandr Kulkov

**DIFFICULTY**:

SIMPLE

**PREREQUISITES**:

Basic combinatorics

**PROBLEM**:

You’re given string S of length N and character X. You have to count the number of substrings of S which contain at least one instance of X.

**QUICK EXPLANATION**:

Calculate substrings which don’t contain X instead.

**EXPLANATION**:

How much substrings does S have? It has N-K+1 substrings of length K thus the total number (summing from substrings of length N to substrings of length 1) may be written as

Now let’s calculate number of substrings which don’t have X and subtract it from total number of substrings. Assume that p_1 < p_2 < \dots < p_k are positions such that S_{p_k}=X. For convenience we may add to them positions p_0=0 and p_{k+1}=N+1.

If substring doesn’t have X in it then it means that both its ends are between consecutive positions p_i and p_{i+1}. How much such substrings is there between p_i and p_{i+1}? Well, it’s exactly the number of substrings in the string S_{p_i+1}S_{p_i+2} \dots S_{p_{i+1}-1}. Its length is len_i = p_{i+1}-p_{i}-1 and amount of its substrings is exactly \tfrac{len_i(len_i+1)}{2}. Subtracting these values for all i from 0 to N we’ll get the answer:

```
vector<int> p = {-1};
for(int i = 0; i < N; i++) {
if(S[i] == X) {
p.push_back(i);
}
}
p.push_back(N);
int ans = N * (N + 1) / 2;
for(size_t i = 1; i < p.size(); i++) {
int len = p[i] - p[i - 1] - 1;
ans -= len * (len + 1) / 2;
}
cout << ans << endl;
```

**AUTHOR’S AND TESTER’S SOLUTIONS**:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.