Beats 5% XD | C++ | Brute Force & Pruning | Pigeon Hole Principle | 2.7 Sec++ LOL
Approach\n Describe your approach to solving the problem. \n1. Precompute all the number of alphabet from 1 until i for 1 \le i \le N.\n2. Calculate every subst
# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Precompute all the number of alphabet from 1 until i for $$1 \\le i \\le N$$.\n2. Calculate every substring that fulfilled the difference between two adjacent characters is at most 2.\n3. Iterate from first until last index of substring.\n4. By Pigeon Hole Principle, we only need to check substring with length $$k*i$$ with $$1 \\le i \\le 26$$\n5. That\'s why my approach almost 3 seconds LOL XD :V\n\n# Complexity\n- Time complexity: $$O(26*26*N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(26N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector< vector<int> > cnt;\n    int calculate(string& word, int byk) {\n        int n = word.size();\n        int ans = 0;\n        \n        for (int i = 0; i<n; i++) {\n            cnt[i+1] = cnt[i];\n            cnt[i+1][(word[i]-\'a\') + 1]++;\n        }\n        \n        for (int i = byk; i<=n; i++) {\n            bool noBreak = true;\n            for (int j = 1; j<=26 && i - j*byk >= 0 && noBreak; j++) {\n                vector<int> ri = cnt[i], le = cnt[i-j*byk];\n                bool flag = true;\n                for (int k = 1; k<=26 && flag && noBreak; k++) {\n                    int itung = ri[k] - le[k];\n                    if (!(itung == byk || itung == 0)) flag = false;\n                    if (itung > byk) noBreak = false;\n                }\n                if (flag) ans++;\n            }\n        }\n        \n        return ans;\n    }\n    \n    int countCompleteSubstrings(string word, int byk) {\n        int n = word.size(), ans = 0;\n        cnt = vector<vector<int>>(n+1, vector<int>(27, 0));\n        string s = "";\n        for (int i = 0; i<n-1; i++) {\n            int now = word[i]-\'a\', nxt = word[i+1]-\'a\';\n            s += word[i];\n            if (abs(nxt-now) > 2) {\n                ans += calculate(s, byk);\n                s = "";\n            }\n        }\n        s+=word[n-1];\n        ans += calculate(s, byk);\n        return ans;\n    }\n};\n```
['C++']