[C++] O(n) filter consecutive substr then count with histogram
Intuition\nTo solve this problem, my initial thought is to break it down into two major steps: identifying potential substrings and then analyzing each to count
# Intuition\nTo solve this problem, my initial thought is to break it down into two major steps: identifying potential substrings and then analyzing each to count the \'complete\' substrings. A \'complete\' substring is one where each character appears exactly \'k\' times or not at all. The key challenge is to do this efficiently, especially since naive methods could lead to prohibitively high complexity.\n\n# Approach\n1. **Identify Potential Substrings**: First, iterate through the given string to find all substrings where the absolute difference between consecutive characters is no more than 2. These substrings are potential candidates within which we might find \'complete\' substrings.\n\n2. **Count Complete Substrings in Each Candidate**: For each candidate substring, use a histogram (frequency count) data structure to keep track of the occurrence of each character. We need to count how many times a particular fixed-length segment (of length \'k\') in the substring meets the criteria of being \'complete\'.\n\n3. **Efficient Histogram Management**: To avoid recomputing the histogram for each segment, maintain a rolling histogram that gets updated as we move through the substring. Additionally, store prefix histograms to quickly calculate the histogram for any segment.\n\n4. **Returning the Total Count**: Sum up the counts of \'complete\' substrings from each candidate substring to get the final result.\n\n# Complexity\n- Time complexity:\n  - The first part of the algorithm, where we identify potential substrings, runs in $$O(n)$$, with \'n\' being the length of the input string. This is because we only need to traverse the string once.\n  - The second part, counting \'complete\' substrings within each candidate, involves examining segments of length \'k\' and checking their histograms. Since we use prefix histograms, the check for each segment is $$O(1)$$, but building these histograms initially takes $$O(n)$$ per candidate substring. If the number of candidate substrings is large, this part could dominate the time complexity.\n\n- Space complexity:\n  - We use extra space for storing the histograms, which is $$O(26 \\times n)$$ for each candidate substring due to the fixed alphabet size (26 for lowercase English letters). However, since we\'re only keeping histograms for one substring at a time, the space complexity is $$O(n)$$.\n  - The space for storing the ranges of potential substrings is at most $$O(n)$$, as in the worst case, each character could start a new range.\n  - Thus, the overall space complexity is $$O(n)$$.\n# Code\n```\nclass Solution {\npublic:\n    // Function to count complete substrings that meet specific criteria.\n    int countCompleteSubstrings(string word, int k) {\n        // Vector to store the ranges (start and end indices) of potential substrings.\n        std::vector<std::pair<int, int>> substr_range;\n\n        int idx = 0; // Index to iterate through the string \'word\'.\n        // Loop through the string.\n        while (idx < word.size()) {\n            int i = idx + 1;\n            // Find the longest substring starting at \'idx\' where the difference between\n            // consecutive characters is not more than 2.\n            for (; i < word.size(); ++i) {\n                if (std::abs(word[i] - word[i - 1]) > 2) {\n                    break;\n                }\n            }\n            // If the found substring\'s length is at least \'k\', add it to \'substr_range\'.\n            if (i - idx >= k) {\n                substr_range.push_back({idx, i});\n            }\n            // Move to the next position.\n            idx = i;\n        }   \n\n        int result = 0; // Variable to store the final result.\n        // Iterate through the found substrings.\n        for (const auto [idx_init, idx_bound] : substr_range) {\n            // Create a string_view of the current substring.\n            const auto substr = std::string_view(word.begin() + idx_init, word.begin() + idx_bound);\n            // Add the count of complete substrings from the current substring to the result.\n            result += count_complete_substr(substr, k);\n        }\n        return result; // Return the total count.\n    }\n\nprivate:\n    // Helper struct to keep track of character frequencies.\n    struct Histo {\n        // Constructor to initialize the frequency array.\n        Histo() {\n            data_.fill(0);\n        }\n\n        // Function to add a character to the histogram.\n        void add(const char ch) {\n            data_[ch - \'a\'] += 1;\n        }\n\n        // Function to check if the histogram satisfies the condition\n        // after removing the frequencies recorded in \'removal\'.\n        bool satisfied(const Histo &removal, const int target) const {\n            for (int pos = 0; pos < data_.size(); ++pos) {\n                const int freq = data_[pos] - removal.data_[pos];\n                // Check if each character either appears \'target\' times or not at all.\n                if ((freq == 0) || (freq == target)) {\n                    continue;\n                }\n                return false;\n            }\n            return true;\n        }\n        // Array to store the frequency of each character.\n        std::array<int, 26> data_;\n    };\n\n    // Function to count complete substrings that satisfy the condition within \'word\'.\n    int count_complete_substr(std::string_view word, const int target) {\n        int total = 0; // Counter for the total number of complete substrings.\n        // Table to store prefix histograms.\n        std::vector<Histo> tbl_prefix_histo;\n        tbl_prefix_histo.reserve(word.size() + 1);\n        tbl_prefix_histo.emplace_back();\n        Histo histo; // Histogram for the current prefix.\n        // Iterate through the string to build prefix histograms.\n        for (int i = 0; i < word.size(); ++i) {\n            histo.add(word[i]); // Add current character to the histogram.\n            tbl_prefix_histo.push_back(histo);\n            // Check for substrings ending at \'i\' and having length multiple of \'target\'.\n            int j = i - target + 1;            \n            for (int cnts = 0; (cnts < 26) && (j >= 0); j -= target, ++cnts) {\n                // Check if the substring satisfies the condition.\n                if (histo.satisfied(tbl_prefix_histo[j], target)) {\n                    ++total; // Increment the total count.\n                }\n            }\n        }\n        return total; // Return the total count of complete substrings.\n    }\n};\n\n```
['C++']