C++ | Sliding Window + Prefix Sum | Deep Dive
Approach\n Describe your first thoughts on how to solve this problem. \nThere can be at most 26 different lengths of the complete substrings: $|1k|$, $|2k|$, \u
# Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\nThere can be at most 26 different lengths of the complete substrings: $|1k|$, $|2k|$, \u2026 $|26k|$. For each length, we can use sliding window where each range is a possible substring. A range will be valid if `isRangeValid() and isFreqValid()` is true.\n```c++\nfor (int l = 0, r = len - 1; r < n; l++, r++) {\n    if (isRangeValid(l, r, prefInvalid) and isFreqValid(freq, k)) {\n        ans++;\n    }\n}\n```\n\n# Implementation\n<!-- Describe your approach to solving the problem. -->\nIn the sliding window, a range `[l, r]` will be valid, if and only if:\n- `isRangeValid(l, r, prefInvalid)` is true $\\rightarrow$ there will be no invalid neighbors in the range having the absolute difference more than 2. `prefInvalid` is the prefix sum array able to query the validity decision in $O(1)$.\n- `isFreqValid(freq, k)` is true $\\rightarrow$ the frequency `freq` of all the characters in the window, is `k`.\n\n#### isRangeValid\n**validNeighbor:** The `ith` element is true if the absolute difference with its previous element is not more than 2.\n```c++\nif (abs(word[i] - word[i - 1]) <= 2) {\n    validNeighbor[i] = true;\n}\n```\n**prefInvalid:** The prefix sum of `false` values from the `validNeighbor`. It\'s goal is to answer the query `isRangeValid` in O(1).\n```c++\nprefInvalid[i] = prefInvalid[i - 1] \n                    + (validNeighbor[i - 1] == false);\n```\n**The range [l, r] will be valid if and only if `(prefInvalid[r] - prefInvalid[l]) = 0`.**\n\n#### isFreqValid\nThe frequency `freq` will be valid if every character `i` in `[l, r]` has `freq[i]` equal to `k`.\n\n#### Example\nLets look at the following example:\n![image.png](https://assets.leetcode.com/users/images/0862fc82-ec0e-4107-a9ac-0b20dee4a03b_1704533295.174379.png)\nIn the prefixSum array, `prefInvalid[r] - prefInvalid[l] = 1`, meaning there is 1 neighbor in the range where the absolute difference is more than 2. So the range is invalid.\n\n# Complexity\n- Time complexity: $O(26^2n)$\n- Space complexity: $O(n)$\n\n# Code\n```\nclass Solution {\npublic:\n    int countCompleteSubstrings(string word, int k) {\n        int n = word.size();\n        \n        vector<int> prefInvalid = getPrefInvalid(word);\n        \n        int ans = 0;\n        for (int i = 1; i <= 26; i++) {\n            int len = k * i;\n            if (len > n) break;\n        \n            vector<int> freq(26);\n            for (int i = 0; i < len - 1; i++) {\n                freq[word[i] - \'a\']++;\n            }\n            for (int l = 0, r = len - 1; r < n; l++, r++) {\n                freq[word[r] - \'a\']++;\n                if (isRangeValid(l, r, prefInvalid) and isFreqValid(freq, k)) {\n                    ans++;\n                }\n                freq[word[l] - \'a\']--;\n            }\n        }\n        \n        return ans;\n    }\n    \nprivate:\n    vector<int> getPrefInvalid(string &word) {\n        int n = word.size();\n        vector<bool> validNeighbor(n);\n        validNeighbor[0] = true;\n        for (int i = 1; i < n; i++) {\n            if (abs(word[i] - word[i - 1]) <= 2) {\n                validNeighbor[i] = true;\n            }\n        }\n\n        vector<int> prefInvalid(n + 1);\n        for (int i = 1; i <= n; i++) {\n            prefInvalid[i] = prefInvalid[i - 1] + (validNeighbor[i - 1] == false);\n        }\n        return prefInvalid;\n    }\n    \n    bool isRangeValid(int l, int r, vector<int> &prefInvalid) {\n        return (prefInvalid[r + 1] - prefInvalid[l + 1]) == 0;\n    }\n    \n    bool isFreqValid(vector<int>& freq, int k) {\n        for (int i = 0; i < 26; i++) {\n            if (freq[i] != 0 and freq[i] != k) {\n                return false;\n            }\n        }\n        return true;\n    }\n};\n```
['Sliding Window', 'Prefix Sum', 'C++']