Count the number of substrings consisting of a single distinct character

In this article, we will discuss the problem of counting the number of substrings consisting of single distinct characters in a given string. We will explore an efficient algorithm to solve this problem and provide C code to implement it.

Problem Statement

Given a string S, the task is to count the number of substrings composed of single distinct characters.

For example, if the input string is "aaaaa", the output should be 15 because there are 15 substrings consisting of single distinct characters. The substrings are "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "a", "aaa ”, “aaa”, “aaaa”, “aaaa”, “aaaa”.

algorithm

We can solve this problem with linear time complexity. We can iterate over the input string and keep track of the current character and the length of the current substring. Whenever a new character is encountered or the end of the string is reached, we can count the number of substrings that can be formed by the current character and the length of the current substring.

Here is a step-by-step algorithm to solve this problem -

• Initialize count and len to 1.

• Iterate over string S from index 1 to n-1.

• If the current character is the same as the previous character, len is increased by 1.

• If the current character is different from the previous character, add (len*(len 1))/2 to count and reset len ​​to 1.

• Return the count.

Let us take the string "aaaaa" as an example to understand the algorithm -

• Initialize count and len to 1.

• Iterate string from index 1 to n-1:

• At index 1, the current character is the same as the previous character, so len is increased by 1.

• At index 2, the current character is the same as the previous character, so len is increased by 1.

• At index 3, the current character is the same as the previous character, so len is increased by 1.

• At index 4, the current character is the same as the previous character, so len is increased by 1.

• We have reached the end of the string, so add (len*(len 1))/2 to count. count = count (5*(5 1))/2 = 15.

• Return the count.

C implementation

This is the C code that implements the above algorithm -

Example

#include<bits/stdc++.h>
using namespace std;

int countSubstrings(string S) {
   int n = S.length();
   int count = 1, len = 1;
   for (int i = 1; i < n; i++) {
      if (S[i] == S[i-1]) {
         len++;
      } else {
         count += (len*(len+1))/2;
         len = 1;
      }
   }
   count += (len*(len+1))/2;
   return count-1;
}

int main() {
   string S = "aaaaa";
   int count = countSubstrings(S);
   cout << count << endl;
   return 0;
}

Output

15

in conclusion

In this article, we discussed the problem of counting the number of substrings consisting of single distinct characters in a given string. We provide an efficient algorithm to solve this problem in linear time complexity and implement it in C. This problem can also be solved using other techniques, but the algorithm above provides

The above is the detailed content of Count the number of substrings consisting of a single distinct character. For more information, please follow other related articles on the PHP Chinese website!