Segment tree solution with unordered map
Intuition\n Describe your first thoughts on how to solve this problem. \nso window can be of any size that are multiple of k \n1k,2k,3k,4k------26k ,for 4k it m
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nso window can be of any size that are multiple of k \n1*k,2*k,3*k,4*k------26*k ,for 4*k it means length of 4*k where 4 chars are distinct and having frequency of each as k . this helps us in finding all substring in o(26*n) time with frequency of each char as k but the other condition that no two adjacent characters should be more than 2 apart .\nto solve this we can use segment tree \nabbac=>1 0 1 2\nabs(a-b) abs(b-b) abs(b-a) abs(a-c) for substring 0,2 we can see that in vector we created from 0,1 if there exist a number greater than 2 than the absolute difference is greater than 2 so this is not a valid substring.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n      void buildTree(vector<int>&tree,vector<int>&a,int index,int s,int e)\n{\n\t//base case\n\tif(s>e)\n\t\treturn;\n\t//reached leaf node\n\tif(s==e)\n\t{\n\t\ttree[index]=a[s];\n\t\treturn ;\n\t}\n\t//now build the segment tree in bottom up manner\n\tint m = (s+e)/2;\n\tbuildTree(tree,a,2*index,s,m);\n\tbuildTree(tree,a,2*index+1,m+1,e);\n\ttree[index]= max(tree[2*index],tree[2*index+1]);\n\treturn;\n}\n\n//function to query the segment tree for RMQ\nint query(vector<int>&tree,int index,int s,int e,int qs,int qe)\n{\n\t//base case: if query range is outside the node range\n\tif(qs>e || s>qe)\n\t\treturn -1;\n\t//complete overlap\n\tif(s>=qs && e<=qe)\n\t\treturn tree[index];\n\t//now partial overlap case is executed\n\tint m = (s+e)/2;\n\tint left_ans = query(tree,2*index,s,m,qs,qe);\n\tint right_ans = query(tree,2*index+1,m+1,e,qs,qe);\n\treturn max(left_ans,right_ans);\n}\n\n//function to update a value at position to "pos"\nvoid updateNode(vector<int>&tree,int index,int s,int e,int pos,int val)\n{\n\tif(pos<s || pos>e)\n\t\treturn ;\n\tif(s==e)\n\t{\n\t\ttree[index] = val;\n\t\treturn ;\n\t}\n\tint m = (s+e)/2;\n\tupdateNode(tree,2*index,s,m,pos,val);\n\tupdateNode(tree,2*index+1,m+1,e,pos,val);\n\ttree[index] = max(tree[2*index],tree[2*index+1]);\n\treturn;\n}\n\n//function to update the values in a range\nvoid updateRange(vector<int>&tree,int index,int s,int e,int rs,int re,int inc)\n{\n\t//query range outside the node range\n\tif(s>re || e<rs)\n\t\treturn;\n\tif(s==e)\n\t{\n\t\ttree[index] += inc;\n\t\treturn ;\n\t}\n\tint m = (s+e)/2;\n\tupdateRange(tree,2*index,s,m,rs,re,inc);\n\tupdateRange(tree,2*index+1,m+1,e,rs,re,inc);\n\ttree[index] = max(tree[2*index],tree[2*index+1]);\n\treturn;\n}\n    int ans=0;\n    int m;\n    bool isvalid(vector<int>&tree,int i,int j,int k,unordered_map<char,int>&mp){\n        int a=query(tree,1,0,m-1,i,j);\n        // cout<<i<<" "<<j<<" "<<a<<endl;\n        if(a>2)return false;\n        bool f=true;\n        for(auto x: mp){\n            // cout<<x.first<<" "<<x.second<<" ";\n            if(x.second!=k){\n                f=false;\n            }\n        }\n        // cout<<endl;\n        return f;\n    }\n    void solve(int i,vector<int>&v,vector<int>&tree,int k,string &word){\n        int len=i*k;\n        if(len>word.length())return;\n        unordered_map<char,int> mp;\n        for(int j=0;j<len;j++){\n            mp[word[j]]++;\n        }\n        if(isvalid(tree,0,len-2,k,mp)){\n            ans++;\n        }\n        for(int j=1;j<=word.length()-len;j++){\n            mp[word[j-1]]--;\n            if(mp[word[j-1]]==0){\n                mp.erase(word[j-1]);\n            }\n            mp[word[j+len-1]]++;\n            if(isvalid(tree,j,j+len-2,k,mp)){\n                ans++;\n            }\n        }\n\n    }\n    int countCompleteSubstrings(string word, int k) {\n        int n=word.size();\n        vector<int> v(n-1);\n        m=n-1;\n        for(int i=0;i<n-1;i++){\n            v[i]=abs(word[i]-word[i+1]);\n        }\n        vector<int> tree(4*n + 1);\n        buildTree(tree,v,1,0,n-2);\n        for(int i=1;i<=26;i++){\n            solve(i,v,tree,k,word);\n\n        }\n        return ans;\n\n\n        \n        \n    }\n};\n```
['C++']