Detail Explain from Intuition into Code. O(n)
Intuition\n Describe your first thoughts on how to solve this problem. \nLet\'s first simplfy the problem by letting k = 1. This means that we want the subarray
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet\'s first simplfy the problem by letting `k = 1`. This means that we want the subarray to only contains unique numbers. Recalls that we can easily get the longest unique subarray that ending at index `i` with sliding window algorithm. and then we can easily calculate the number of subarrays which ends at `i` that have unique numbers.\n\nThe intuition I got from the above example is:\nfor `k > 1`. for every subarrays that ends at `i`, we only need to consider the subarrays that start between `[l, m]` and ends at `i` as shown below (assume `k = 2`) that satisfy the problem\'s requirements\n```\nc abes c adef c\n^      ^      i\n|      | \n|      |\nl      m\n\n```\n\n\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int countCompleteSubstrings(String word, int k) {\n        int start = 0;\n        int res = 0;\n        int[][] prefixCnt = new int[word.length() + 1][26];\n        for (int i = 0; i < word.length(); ++i) {\n            System.arraycopy(prefixCnt[i], 0, prefixCnt[i + 1], 0, 26);\n            prefixCnt[i + 1][word.charAt(i) - \'a\'] += 1;\n        }\n        for (int i = 0; i < word.length() - 1; ++i) {\n            if (Math.abs(word.charAt(i) - word.charAt(i + 1)) > 2) {\n                res += getCnt(word, start, i, k, prefixCnt);\n                start = i + 1;\n            }\n        }\n        res += getCnt(word, start, word.length() - 1, k, prefixCnt);\n        return res;\n    }\n    private int getCnt(String word, int start, int end, int k, int[][] prefixCnt) {\n        int res = 0;\n        Queue<Integer>[] index = new Queue[26];\n        for (int i = 0; i < index.length; ++i) index[i] = new ArrayDeque<>();\n        for (int i = 0; i < end - start + 1; ++i) {\n            int idx = start + i;\n            index[word.charAt(idx) - \'a\'].offer(idx);\n\n            if (index[word.charAt(idx) - \'a\'].size() >= k) {\n                int left = index[word.charAt(idx) - \'a\'].size() == k ? start : (index[word.charAt(idx) - \'a\'].poll() + 1);\n                int right = index[word.charAt(idx) - \'a\'].peek();\n                int[] cnt = getRangeCnt(prefixCnt, left, idx + 1);\n                for (int j = left; j <= right; ++j) {\n                    if (valid(cnt, k)) ++res;\n                    --cnt[word.charAt(j) - \'a\'];\n                }\n            }\n        }\n        return res;\n    }\n    private int[] getRangeCnt(int[][] prefixCnt, int start, int end) {\n        int[] res = new int[26];\n        for (int i = 0; i < 26; ++i) {\n            res[i] = prefixCnt[end][i] - prefixCnt[start][i];\n        }\n        return res;\n    }\n    private boolean valid(int[] arr, int k) {\n        for (int a : arr) {\n            if (a == 0) continue;\n            if (a != k) return false;\n        }\n        return true;\n    }\n}\n```
['Java']