STRCH - Editorial

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

1+2+\dots+N = \tfrac{N(N+1)}{2}

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.

1 Like

Hmmm… … . .
Here is my approach, slightly diffrent. For every char match, I am finding the number of sequences such that the char at the position is the first in the sequences.