题解 | #游戏机本当下手#

游戏机本当下手

用一个数组记录 $A$ 字符发生变化 $(s[i] \ne s[i + 1])$ 的下标，这些下标代表每一段连续相同的字符结束的位置。除此之外，

在数组开头加上 $-1$ ：因为第一段连续相同的字符是从下标 $0$ 处开始的，我们想象字符串前面一段虚拟的字符，那段字符应该在在下标 $-1$ 处结束。
在数组末尾加上 $n - 1$ ：因为最后一段连续相同的字符会在字符串结尾时结束，这是我们 $(s[i] \ne s[i + 1])$ 这个条件判断不了的。

基于我们记录的数据，我们可以发现对于第 $i$ 段连续相同的字符：

这段连续字符应该从 $A[i - 1] + 1$ ，也就是上一段连续字符结束位置的下一个字符开始。
这段连续字符应该从 $A[i]$ ，也就是当前这段连续字符的结束位置结束。
因此第 $i$ 段连续相同的字符长度为 $A[i] - (A[i - 1] + 1) + 1 = A[i] - A[i - 1]$ 。

当 $k = 1$ 时，

我们考虑的其实是每一段连续相同的字符可以取多少种子串，假设这段连续相同的字符长度为 $len$ , 那么这个数量是 $\frac{len(len + 1)}{2}$ 。

因此在这种情况，我们需要遍历每一段连续的字符串，计算长度，将对应的子串数量累加到最终答案。

当 $k \ne 1$ 时，

我们考虑的其实是第 $i, i + 1, \cdots, i + k - 2, i + k - 1$ 段连续相同的字符。因为子串要求连续，所以对于这段子串

第 $i + 1$ 到第 $i + k - 2$ 段字符必须全在字串内
第 $i$ 段连续相同的字符中，至少需要取 $1$ 个字符，假设第 $i$ 段连续相同的字符长度为 $len1$ ，一共有 $len1$ 中不同的取法(取 $1, 2, \cdots, len1$ 个)
第 $i + k - 1$ 段段连续相同的字符中，至少需要取 $1$ 个字符，假设第 $i + k - 1$ 段连续相同的字符长度为 $len2$ ，一共有 $len2$ 中不同的取法(取 $1, 2, \cdots, len2$ 个)
所以这种情况下，字符串一共有 $len1 \times len2$ 种取法

因此在这种情况下，

我们可以遍历每一段连续相同的字符，对于第 $i$ 段连续相同的字符作为子串起始点，计算当前段的长度 $len1$ ，以及第 $i + k - 1$ 段的长度 $len2$ ，将 $len1 \times len2$ 累加到最终答案。
或者遍历每一段连续相同的字符，对于第 $i$ 段连续相同的字符作为子串终止点，计算当前段的长度 $len1$ ，以及第 $i - k + 1$ 段的长度 $len2$ ，将 $len1 \times len2$ 累加到最终答案。

fmin = lambda x, y: x if x < y else y
fmax = lambda x, y: x if x > y else y

def solve(testcase):
    n, k = MI()
    s = I()

    A = [-1]
    for i in range(n - 1):
        if s[i + 1] != s[i]:
            A.append(i)
    A.append(n - 1)

    res = 0
    if k == 1:
        for i in range(1, len(A)):
            LEN = A[i] - A[i - 1]
            res += LEN * (LEN + 1) // 2

    else:
        for i in range(k, len(A)):
            res += (A[i] - A[i - 1]) * (A[i - k + 1] - A[i - k])
    
    print(res)

for testcase in range(1):
    solve(testcase)