Number of Equal Count Substrings - CPP Solution

1. Introduction

This blog post explores a unique string processing challenge in C++ known as the "Number of Equal Count Substrings" problem. This problem tests the ability to analyze and count specific substrings in a string based on character frequency, showcasing string traversal and frequency counting techniques.

Problem

The task is to find the number of substrings where each character appears the same number of times. For example, in the string "aabb", "aa", "bb", "aabb", and "bbaa" are valid substrings.

2. Solution Steps

1. Iterate over all possible substrings of the string.

2. For each substring, count the frequency of each character.

3. Check if all characters in the substring have the same frequency.

4. Increment a counter every time a substring meets the criteria.

5. Return the total count of such substrings.

3. Code Program

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

// Helper function to check if all characters in a substring have the same frequency
bool allCharsSameFreq(const unordered_map<char, int>& freq) {
    int sameFreq = -1;
    for (const auto& p : freq) {
        if (sameFreq == -1) {
            sameFreq = p.second;
        } else if (p.second != sameFreq) {
            return false;
        }
    }
    return sameFreq != -1;
}

// Function to count substrings where each character has the same frequency
int countEqualFreqSubstrings(string s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        unordered_map<char, int> freq;
        for (int j = i; j < s.length(); j++) {
            freq[s[j]]++;
            if (allCharsSameFreq(freq)) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    string s = "aabb";
    cout << "Number of equal count substrings: " << countEqualFreqSubstrings(s) << endl;
    return 0;
}

Output:

Number of equal count substrings: 4

Explanation:

1. The input string "aabb" is processed to find substrings where each character appears with the same frequency.

2. Substrings "aa", "bb", "aabb", and "bbaa" are identified as valid since the frequency of 'a' and 'b' is equal in each.

3. The function iterates through the string, analyzing all possible substrings and counting their character frequencies.

4. A helper function checks if all characters in a substring have the same frequency.

5. The total count of 4 reflects the number of substrings meeting the criteria.

6. This method demonstrates an effective approach to counting specific substrings based on character frequency in C++.