algorithm - 找到长度为K的良好子串，使其重要性最低

将一个好的子串定义为以“x”开头、以“z”结尾且长度可被3整除的子串将字符串的重要性定义为它与之相交的好的子字符串的数量（如果它本身是好的，则不包括它本身）考虑由x，y，z组成的长度为N（1≤N≤10^5）的字符串。给定一个整数K（1≤K≤10^5），找到具有最小重要性且长度为K的好子字符串。需要打印最小重要性。
我有一个解决这个问题的想法，但我不能真正地编码它首先，必须在线性/线性时间内完成。
我的想法是，在beg[I]存储源于I的好的子串的数量。如果我们使用一个从右端开始的计数器，并根据“z”的模3位置向右相加，就可以做到这一点如果i%3==j，那么beg[i]=i右边位置j+2 mod 3中的“z”个数。类似地，我们可以创建end[i]来获得以i结尾的好子串的个数。如果i位置包含“y”，或者如果它不构成好的子串，我们将写beg[i]或者end[i]等于0。
现在对于下一部分（寻找交集），我不确定如何得到线性/线性解。
对于特定的区间[arr[i]，arr[i+K-1]]，交叉口的数量为
=在[i]之前开始的子串数量-在[i]之前结束的子串数量+在[i]之后开始并在[i+k-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)