我试图从黑客级别解决这个问题我尝试了蛮力解决方案，但它似乎不起作用。有人可以给一个想法来有效地解决这个问题。 https://www.hackerrank.com/contests/sep13/challenges/sherlock-puzzle
给定一个包含 '0' 和 '1' 的二进制字符串 (S) 和一个整数 K，求 (S * K) 的最长连续子序列的长度 (L)，使得零的数量的两倍 <= 的数量的三倍那些 (2 * #0s <= 3 * #1s) 在那个序列中。
S * K 定义如下： S * 1 = S S * K = S + S * (K - 1)
输入格式 第一行（也是唯一的）包含一个整数 K 和由单个空格分隔的二进制字符串 S。
约束 1 <= |S| <= 1,000,000 1 <= K <= 1,000,000
输出格式 单个整数 L - 测试用例的答案
蛮力显然是行不通的，因为它是O((n * k) ** 2). 我将在这个答案中使用 python 样式的列表推导。你需要一个数组t = [3 if el == "1" else - 2 for el in S]。现在，如果您使用p[i] = t[0] + ... + t[i]数组，您可以看到，在这种k == 1情况下，您基本上是在寻找一对 (i, j)，i < jp[j] - (p[i - 1] if i != 0 else 0) >= 0是正确的，并且j - i在这些对中是最大的。现在，对于每一个i in 0..n-1你必须找到它的j对，使得上述是最大的。这可以O(log n)针对特定情况完成，i因此这为O(n log n)k == 1 情况提供了解决方案。这可以扩展到O(n log n)一般情况的解决方案（有一个技巧可以找到可以覆盖的最大块）。此问题也有O(n)解决方案，但您需要进一步检查p顺序。不过，我不建议用脚本语言编写解决方案。甚至O(n)解决方案在python中也会超时......
这里有一个提示：
让我们首先假设 K = 1 并且 S 看起来像（使用点表示 0）：
..1...11...11.....111111....111....
e f b a c d
关键是要注意，如果最长的可接受序列包含 a1它也将包含任何相邻的序列。例如，如果最长的序列在a处包含 1，那么它也将包含b和c（包括）之间的所有序列。
所以你只需要在块所在的点分析序列。
主要问题是：如果你从某个区块开始，你能进入下一个区块吗？例如，如果您从e开始，则可以到达f处的块，但不能到达b。如果您从b开始，您可以到达d等处的街区。
然后推广 K > 1 的分析。