Sparse Table Fast Skip Valid Substrings LOL
I completely missed the intuition of 26 different sliding windows, so I instead thought of the following:\n\nChecking for every complete substring that ends at 
I completely missed the intuition of 26 different sliding windows, so I instead thought of the following:\n\nChecking for every complete substring that ends at index `i`. We need to know two things:\n1. What\'s the maximum index `j` such that `j <= i` `word[j..i]` contains `k` occurences of `word[i]`?\n2. What are the other characters that I will encounter in `word[j..i]`?\n\nWith those information, we can perform "fast jumping", where we have to make sure every character included currently has `k` occurences. We can use a sparse table to query the bitmask of characters within a range and precompute the information to jump to the correct position for each charaacter at each index.\n\nWe can have separate adjacent complete substrings, so once we find a complete substring, we also consider extending the left range by 1, to see if we can get another complete substring.\n\n```\nprivate class SparseTable(v: String, val k: Int = 25) {\n    val n = v.length\n    val dp = IntArray(n * (k + 1))\n\n    init {\n        for ((i, c) in v.withIndex()) dp[i] = 1 shl (c - \'a\')\n        for (i in 1..k) for (j in 0..n - (1 shl i)) {\n            val a = dp[(i - 1) * n + j]\n            val b = dp[(i - 1) * n + j + (1 shl (i - 1))]\n            dp[i * n + j] = a or b\n        }\n    }\n\n    fun queryFast(l: Int, r: Int): Int { // only works if operation is idempotent!\n        val p = 31 - (r - l + 1).countLeadingZeroBits()\n        val a = dp[p * n + l]\n        val b = dp[p * n + (r - (1 shl p) + 1)]\n        return a or b\n    }\n}\n\nprivate class SparseTable2(v: BooleanArray, val k: Int = 25) {\n    val n = v.size\n    val dp = v.copyOf(n * (k + 1))\n\n    init {\n        for (i in 1..k) for (j in 0..n - (1 shl i)) {\n            val a = dp[(i - 1) * n + j]\n            val b = dp[(i - 1) * n + j + (1 shl (i - 1))]\n            dp[i * n + j] = a and b\n        }\n    }\n\n    fun queryFast(l: Int, r: Int): Boolean { // only works if operation is idempotent!\n        val p = 31 - (r - l + 1).countLeadingZeroBits()\n        val a = dp[p * n + l]\n        val b = dp[p * n + (r - (1 shl p) + 1)]\n        return a and b\n    }\n}\n\nclass Solution {\n    fun countCompleteSubstrings(word: String, k: Int): Int {\n        val n = word.length\n        val pos = Array(26) { ArrayList<Int>() }.also {\n            for (i in 0 until n) it[word[i] - \'a\'].add(i)\n        }\n        val pos2 = Array(n + 1) { IntArray(26) }.also {\n            for (a in 0 until 26) for (i in k - 1 until pos[a].size) it[pos[a][i] + 1][a] = pos[a][i - k + 1] + 1\n            for (i in 0 until n) for (a in 0 until 26) it[i + 1][a] = max(it[i][a], it[i + 1][a])\n        }\n        val cnt = Array(n + 1) { IntArray(26) }.also {\n            for (i in 0 until n) for (a in 0 until 26) it[i + 1][a] = it[i][a] + (if (a == word[i] - \'a\') 1 else 0)\n        }\n        val good = BooleanArray(n).also {\n            for (i in 0 until n - 1) if (abs(word[i] - word[i + 1]) <= 2) it[i] = true\n        }\n        val st = SparseTable(word)\n        val st2 = SparseTable2(good)\n        var ans = 0\n        for (i in 0 until n) {\n            var j = i\n            var m = 0\n            var vis = 0\n            outer@ while (j >= 0) {\n                m = m or (1 shl (word[j] - \'a\'))\n                var new_j = j\n                while (m > 0) {\n                    val u = 31 - m.countLeadingZeroBits()\n                    if (vis and (1 shl u) > 0 || pos2[j + 1][u] == 0) break@outer\n                    vis = vis or (1 shl u)\n                    new_j = min(new_j, pos2[j + 1][u] - 1)\n                    val m2 = st.queryFast(new_j, i) and vis.inv()\n                    m = m xor (1 shl u) or m2\n                }\n                for (a in 0 until 26) if (vis and (1 shl a) > 0 && cnt[i + 1][a] - cnt[new_j][a] != k) break@outer\n                if (new_j != i && !st2.queryFast(new_j, i - 1)) break\n                ans++\n                j = new_j - 1\n            }\n        }\n        return ans\n    }\n}\n```
['Sliding Window', 'Kotlin']