Sliding Window | Complete Explanation
Intuition\nThis is a very tricky problem.\nBrute force could be to iterate on all the substrings and check if they are complete and if they are then increment t
# Intuition\nThis is a very tricky problem.\nBrute force could be to iterate on all the substrings and check if they are complete and if they are then increment the result. TC of this would be $$O(n^3)$$, $$O(n^2)$$ for iterating on all substrings and $$O(n)$$ to check if a substring is complete or not.\n\nA little optimization to this would be using Sliding window. If I am at an index $$i$$, I will try to calculate the number of substrings ending at index $$i$$. I\'ll keep a window such that each of the adjacent element has a difference of atmost $$2$$. \nOnce I find a valid window I will try to check if the count of current value in the this window is $$k$$ or not and if it is I\'ll try to shorten the window size by one each time and check if the all chcaracter\'s in the window occur exactly $$k$$ times or not.\nIf the count of the current character is greater then $$k$$ then I\'ll try to reduce the window size until and unless the count of the current character becomes $$k$$. \nIn this way I can sum up the number of complete substrings ending at every index and return the ans.\nTC would be $$O(26*n*n)$$ which would give TLE.\n\nThe code to the above inutition is given below.\n\n    class Solution {\n    public:\n        bool checkEqualToK(vector<int>&cnt,int k){\n            for(int i=0;i<26;++i){\n                if(cnt[i] == 0) continue;\n                if(cnt[i] != k) return false;\n            }\n            return true;\n        }\n\n        int countCompleteSubstrings(string s, int k) {\n            int res = 0,n=s.size();\n            int st=0;\n            vector<int>cnt(26,0);\n            for(int e=0;e<n;++e){\n                cnt[s[e]-\'a\']++;\n                if(e and abs(s[e]-s[e-1]) > 2){\n                    cnt = vector<int>(26,0);\n                    cnt[s[e]-\'a\']++;\n                    res += checkEqualToK(cnt,k);\n                    st = e;\n                }else if(cnt[s[e]-\'a\'] == k){\n                    vector<int>x = cnt;\n                    for(int i=0;i<26;++i) x[i] = cnt[i];\n                    int i=st;\n                    do{\n                        res += checkEqualToK(x,k);\n                        x[s[i++]-\'a\']--;\n                    }while(i<=e);\n                }else if(cnt[s[e] - \'a\'] > k){\n                    while(cnt[s[e]-\'a\'] > k) cnt[s[st++]-\'a\']--;\n                    cnt[s[e--]-\'a\']--;\n                }\n            }\n            return res;\n        }\n    };\n\nFor themost optimized appraoch one observation has to be made. There can be a maximum of $$26$$ unique character\'s in a window. If each character occurs $$k$$ times then the maximum length of the window will be $$k*26$$. The size of the window is bounded by that. The minimum window size will be when there is only one unique character in a window and it occurs $$k$$ tiems, hence window size will be $$k*1$$. \n\nHence, the different window sizes which are possible will be $$k*1,k*2,k*3....k*26$$.\nIf I try to calculate the number of complete substrings in each of these window sizes then I can sum up my ans in $$O(n*26)$$. \n\nCalcultaing the answer for a particular window size will take a maximum of $$O(n)$$ time, as the number of winoows with size $$x$$ in a string of size $$n$$ would be $$n-x+1$$.\n\n    cnt += curr==k?1:curr==k+1?-1:0;\n\n$$cnt$$ measures the count of unique character\'s in window. If the number of unique character\'s in window are $$len/k$$ where $$len$$ is the size of the window being considered, then it is a valid window.\n\nHere the moment the count of a particular character reaches $$k$$ then we increment by $$1$$ indicating that one unique character has occured $$k$$ times.The first time the size of character becomes greater than $$k$$ meaning $$k+1$$ then we decrement the number of unique character\'s which occur exactly $$k$$ times by one.\n\nNote that I am not decrementing count when $$curr>k$$ as when $$curr$$ becomes $$k+2$$ I will again decrement $$cnt$$ by $$1$$ which is wrong.\n\n    if(e and abs(s[e] - s[e-1]) > 2){\n        memset(v,0,sizeof(v));\n        v[s[st=e]-\'a\']++;\n        cnt = v[s[st]-\'a\']==k;\n    }\n\nThe moment, the difference between the adjacent character\'s becomes greater than $$2$$, I have to start a new window as including the character in the current window makes the window become invalid. \nSo I reinitialize the $$cnt$$ array and increment the count of current character by $$1$$ if the condition is satififed. The condition will only be satisfied only when $$k$$ is $$1$$ here.\n\n    cnt += curr==k?1:curr == k-1?-1:0;\n\nHere, once the length of the current window becomes $$len$$ I check if it consists of $$k$$ character\'s or not and if it does increment by one. \nAfter this I try to remove the character from the front to maintain the window size, After removing I have to update the $$cnt$$. \nIf after the removing the current char from the window, the $$cnt$$ becomes $$k$$ it means, it was $$k+1$$ first and now it became $$k$$ which means I have to increment the number of unique character\'s, else if it becomes $$k-1$$ it means it was $$k$$ which means it was a unique character already occuring $$k$$ times but now it occurs $$k-1$$ times hence decrement the count.\n\n**Note :** Using an unordered map was giving me TLE, hence in these kind of questions we can take a normal vector or an array of size $$26$$ to keep the frequency of each character.\n\n# Complexity\n- Time complexity: $$O(n*26)$$\n- Space complexity: $$O(26)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int cnt_(string &s,int k,int len){\n        int st = 0,res=0,cnt=0;\n        int n=s.size();\n        if(len==1) return n;\n        int v[26]={};\n        for(int e=0;e<n;++e){\n            int curr = ++v[s[e]-\'a\'];\n            cnt += curr==k?1:curr==k+1?-1:0;\n            if(e and abs(s[e] - s[e-1]) > 2){\n                memset(v,0,sizeof(v));\n                v[s[st=e]-\'a\']++;\n                cnt = v[s[st]-\'a\']==k;\n            }else if(e - st+1 == len) {\n                int curr = --v[s[st++]-\'a\'];\n                res += (cnt==len/k);\n                cnt += curr==k?1:curr == k-1?-1:0;\n            }\n        }\n        return res;\n    }\n\n    int countCompleteSubstrings(string word, int k) {\n        int res=0;\n        for(int i=1;i<=26;++i) res += cnt_(word,k,k*i);\n        return res;\n    }\n};\n```
['C++']