找到长度K的好子串，使它的重要性最小。

Question

将一个好子字符串定义为以'x‘开头，以'z’结尾，长度可被3整除的子字符串。定义字符串的重要性是它与之相交的好子字符串的数量(如果它本身是好的，则不包括它自己)。考虑一个长度为N (1≤N≤10^5)的字符串，它由x，y，z组成，给定一个整数K(1≤K≤10^5)，找到具有最小重要性且长度K的好子串，需要打印最小重要性。

我有一个解决这个问题的主意，但我真的不能把它编码出来。首先，它必须在线性/线性时间内完成。

我想的是，把源自我的好的子串的数量存储在贝基，如果我们从右边使用一个计数器，然后按照“z”的模3位置往右加，就可以做到这一点。如果i%3==j，则begi=number of 'z‘在位置j+2 mod 3的右边。类似地，我们可以创建endi，以得到以i结尾的好子字符串的数量。如果我的位置包含'y’，或者如果它没有形成一个好的子字符串，那么我们将编写等于0的begi或endi。

现在，对于下一部分(找到交叉口)，我不知道如何得到线性/线性的解。对于特定的间隔[arri，arri+K-1]，交叉口的数目为

=在ai之前开始的子串，在ai+K-1之前结束，在ai之后结束，在ai +K-1之后结束。

这就是我的想法。我确信有一些方法可以进行预计算，也许可以修改我所写的方程式，从而得出答案。

Answer 1

请注意，累加i=索引i或更大值上开始的好字符串数。答案公式可能有错误，但这个想法应该是正确的。

for i = 0 to N
    beg[i] = end[i] = 0

for i = 0 to 3
    z[i] = 0
    x[i] = 0

for i = 0 to N
    if str[i] == 'z'
        z[i % 3]++

for i = 0 to N
   if str[i] == 'z'
       z[i % 3]--
       end[i] = x[i % 3]
   if str[i] == 'x'
       beg[i] = z[i % 3]
       x[i % 3]++
       total += beg[i]

for i = 0 to N
    accumulated[i] = total
    total -= beg[i]

answer = N + 1

beforeStart = beforeEnd = 0
for i = 0 to N - k
    if str[i] == 'x' and str[i + k] == 'z'
        answer = min(answer, beforeStart - beforeEnd + (accumulated[i + k] - accumulated[i]) + beg[i] - 1)

    beforeStart += beg[i]
    beforeEnd += end[i]

print(answer)