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

Question

Define a good substring as a substring which begins with 'x', ends with 'z' and has a length divisible by 3. Define the importance of a string as the number of good substrings it intersects with (excluding itself, if it is itself good). Consider a string of length N (1≤N≤10^5) which is composed of x,y,z. Given an integer K(1≤K≤10^5), find the good substring that has the minimum importance and is of length K. You need to print the minimum importance.

我有解决此问题的想法，但我无法真正将其编写出来。首先，它必须在线性/线性算术时间内完成。

我的想法是，在 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]]，交叉点的数量将是

= num of substrings which begin before a[i] - num of subs which end before a[i] + number of subs that beginning after a[i] and ends before, at, after a[i+K-1] ].

这就是想法。我确信有一些方法可以进行预计算，并且可以修改我写的上述等式以得出答案。

Answer 1

请注意，accumulated[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)