Count Substrings with Only One Distinct Letter - CPP Solution

1. Introduction

This blog post covers a string processing problem in C++ that involves counting substrings with a specific characteristic. The challenge is to count the number of substrings within a given string where all characters are the same.

Problem

Given a string, the task is to count the number of substrings that contain only one distinct letter.

2. Solution Steps

1. Initialize a count variable to keep track of the number of valid substrings.

2. Iterate through the string.

3. For each character, count the length of the contiguous substring of the same character.

4. Calculate the number of substrings that can be formed with this contiguous substring and add it to the count.

5. Return the total count of valid substrings.

3. Code Program

#include <iostream>
#include <string>
using namespace std;

// Function to count substrings with only one distinct letter
int countLetters(string s) {
    int count = 0, consecutive = 1;

    for (int i = 1; i <= s.size(); i++) {
        if (i < s.size() && s[i] == s[i - 1]) {
            consecutive++;
        } else {
            // Add the number of substrings for the contiguous characters
            count += (consecutive * (consecutive + 1)) / 2;
            consecutive = 1; // Reset for the next character
        }
    }
    return count;
}

int main() {
    string s = "aaaba";
    cout << "Count of substrings with one distinct letter: " << countLetters(s) << endl;
    return 0;
}

Output:

Count of substrings with one distinct letter: 8

Explanation:

1. The input string "aaaba" is evaluated to count substrings with only one distinct letter.

2. The contiguous substrings "aaa", "aa", "a", "a", "a", "aa", "b", and "a" are identified.

3. The count for each substring is calculated using the formula (n * (n + 1)) / 2, where n is the length of the contiguous substring.

4. The total count of 8 represents the number of such substrings in the input string.

5. The approach uses a single pass over the string, efficiently calculating the required count.