2 Solutions | Brute Force, Sliding Window
Solution-1: Brute Force -- (TLE -- 717 / 759 TCs passed. -- 94.46%)\n\n### Idea:\n+ Generate all possible substrings - O(N^2).\n+ Check if each substring is com
# Solution-1: Brute Force -- (TLE -- 717 / 759 TCs passed. -- 94.46%)\n\n### Idea:\n+ Generate all possible substrings - O(N^2).\n+ Check if each substring is complete & increment count - O(N).\n\n### Complexity:\n+ **Time:** `O(N^3)`\n+ **Space:** `O(N)`\n\n\n### CODE:\n```\nclass Solution {\npublic:\n    int countCompleteSubstrings(string word, int k) \n    {\n\t    // SOL-1: Brute force -- TC: O(N^3), SC: O(N*N) -- TLE -- 717 / 759 TCs passed -- 94.46%\n        return sol1BruteForce(word, k);\n    }\n\nprivate:\n    // TC: O(N^3), SC: O(N*N)\n    int sol1BruteForce(const string &word, int k) \n    {\n        int n = word.size();\n        int count = 0;\n\n        for ( int i = 0; i < n; ++i ) \n        {\n            string substr = "";\n            for ( int j=i; j<n; ++j ) \n            {\n                substr += word[j];\n                if ( isSubstringComplete(substr, k) )\n                    ++count;\n            }\n        }\n\n        return count;\n    }\n\n    // TC: O(N), SC: O(1)\n    bool isSubstringComplete(const string &s, int k) \n    {\n        int freq[26] = {0};\n        freq[s[0]-\'a\']++;\n        for ( int i=1; i<s.size(); i++ ) {\n            if ( abs(s[i] - s[i-1]) > 2 )\n                return false;\n            freq[s[i]-\'a\']++;\n        }\n\n        for ( int i = 0; i < 26; ++i ) \n        {\n            if ( freq[i] == 0 || freq[i] == k ) continue;\n            else return false;\n        }\n        return true;\n    }\n};\n```\n\n# Solution-2: Sliding Window\n### Complexity:\n+ **Time:** O(N)\n+ **Space:** O(N)\n### CODE:\n```\nclass Solution {\npublic:\n    int countCompleteSubstrings(string word, int k) \n    { \n        // SOL-2: SW -- TC: O(N), SC: O(1)\n        return sol2SlidingWindow(word, k);\n    }\n\nprivate:\n    // SOL-2: SW -- TC: O(N), SC: O(1)\n    int sol2SlidingWindow(const string &word, int k) \n    {\n        int result = 0;\n\n        // Iterate over possible number of distinct characters\n        for (int distinctChars = 1; distinctChars <= min((int)word.size() / k, 26); ++distinctChars) \n        {\n            int charCount[26] = {};  // Array to store character frequencies\n            int exactCount = 0;      // Count of characters with exactly k occurrences\n            int windowSize = distinctChars * k;  // Desired window size\n\n            // Sliding window approach\n            for ( int right = 0, left = 0; right < word.size(); ++right ) \n            {\n                // Reset the window if adjacent characters differ by more than 2\n                if ( right && (abs(word[right] - word[right - 1]) > 2) ) {\n                    memset(charCount, 0, sizeof(charCount));\n                    exactCount = 0;\n                    left = right;\n                }\n\n                // Update character frequency and exact count\n                int reps = ++charCount[word[right] - \'a\'];\n                exactCount += (reps == k) ? 1 : (reps == k + 1) ? -1 : 0;\n\n                // Check if the current window size is at least the desired size\n                if (right - left + 1 >= windowSize) {\n                    // Adjust the window size if it exceeds the desired size\n                    if (right - left >= windowSize) {\n                        int reps = --charCount[word[left++] - \'a\'];\n                        exactCount += (reps == k) ? 1 : (reps == k - 1) ? -1 : 0;\n                    }\n\n                    // Increment result if the exact count matches the number of distinct characters\n                    result += (exactCount == distinctChars);\n                }\n            }\n        }\n\n        return result;\n    }\n};\n```
['C', 'Sliding Window']