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.
