Problem Link:
Author: Mohammad Shahhoud & Said Sryhini
Tester: Hasan Jadouh
Editorialist: Said Sryheni
Difficulty:
Easy
Prerequisites :
Counting, Combinatorics
Problem:
Given a string A of lowercase English letters, find the number of good substrings. A substring A[L,?R] is good if:
-
The length of the substring is exactly 2 and A_L = A_R, OR
-
The length of the substring is greater than 2,A_L = A_R, and the substring A[L+1,R-1] has only one distinct letter.
Explanation:
First let’s think about examples of a good substring. The following are all good substrings: {aa, abbbba, aaaaaa}. So, a good substring actually has two types:
-
It’s either a substring whose size is greater than or equal to 2, and contains one distinct letter only.
-
Or it’s a substring whose size is exactly greater than 2, the first and the last letter are the same, while the indexes inside contain one distinct letter, which is different from the first and the last one.
Now, let’s change the string into a simpler form. Let’s devide the original string into groups, such that all the consecutive indexes having the same letter, will be joined in one group. For example the string S = aabccbbbbe, can be represented as S = {aa, b, cc, bbbb, e}.
To calculate the number of good substrings that correspond to the first type we can simply calculate the answer for each group separetely. Note that the answer for each group depends only on the size of the group (let’s denote it as N). The problem is reduced in this situation to finding the number of pairs that can form the starting and ending indexes of a good substring. The answer can be calculated using combinations:
C(N, 2) = \frac{N . (N - 1)}{2}
Calculating the number of good substrings that correspond to the second type is actually much simpler. Iterate over all the groups, and whenever you find a group such that the two groups to its left and right consist of the same letter, add 1 to your final answer.
Time Complexity: O(N)
Check setter and tester solutions for the implementation.
