O(N) solution in C++
The key is to enumerate all possible distinct counts of chars, which should be in [1, 26]\n\n1 For any index as the end of the substring, it has a max of 26 dis
The key is to enumerate all possible distinct counts of chars, which should be in [1, 26]\n\n1 For any index as the end of the substring, it has a max of 26 distinct lengths of the complete substring, with length k, 2k, ..., 26k. \n2 To check if they are k repeat, we can use a prefix sum of frequencies, so for each length, we can check if they are valid in O(26).\n3 To fulfill the adjacent difference, record the left most position, once the difference condition failed, reset it with current index.\n\nTime Complexity O(26^2 * n), space  O(26 * n).\nTime limit constant is very strict during contest so use array instead of vector.\n\n\tclass Solution {\n\t\t\tusing Freq = array<int, 26>;\n\t\tpublic:\n\t\t\tint countCompleteSubstrings(string word, int k) {\n\t\t\t\tint n = word.size();\n\t\t\t\tvector<Freq> freqs(n + 1);\n\t\t\t\tfor(int i = 0; i < n; i++){\n\t\t\t\t\tfreqs[i+1] = freqs[i];\n\t\t\t\t\tfreqs[i+1][word[i] - \'a\']++;\n\t\t\t\t}\n\t\t\t\tint l = 0;\n\t\t\t\tint res = 0;\n\t\t\t\tfor(int i = 0; i < n; i++){\n\t\t\t\t\tif(i >= 1 && abs(word[i] - word[i-1]) > 2){\n\t\t\t\t\t\tl = i;\n\t\t\t\t\t}\n\t\t\t\t\tfor(int c = 1; c <= 26; c++){\n\t\t\t\t\t\tint len = c * k;\n\t\t\t\t\t\tint start = i - len + 1;\n\t\t\t\t\t\tif(start < l) break;\n\t\t\t\t\t\tFreq diff_freq;\n\t\t\t\t\t\tint kcnt = 0;\n\t\t\t\t\t\tfor(int j = 0; j < 26; j++){\n\t\t\t\t\t\t\tdiff_freq[j] = freqs[i+1][j] - freqs[start][j];\n\t\t\t\t\t\t\tif(diff_freq[j] == k) kcnt++;\n\t\t\t\t\t\t\tif(diff_freq[j] >0 && diff_freq[j] != k) break;\n\t\t\t\t\t\t}\n\t\t\t\t\t\tif(kcnt == c) res++;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\treturn res;\n\n\t\t\t}\n\t\t};
[]