CK87GSUB - Editorial

Problem Link:

Practice
Contest

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:

  1. It’s either a substring whose size is greater than or equal to 2, and contains one distinct letter only.

  2. 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.

Solution 1
Solution 2

2 Likes

Good question !! :slight_smile:
It made me think that since we have to calculate all good strings, we have to find every next of occurrence of every letter. For every letter, i was trying to find all the possible strings in (n^2).
But since all letters same was a special case it could have been handled separately and the second case will only take O(N) since now we are only bothered about next occurrence of every letter which could easily be found in O(N).