python - A 和 B 的计数差异最大的最短子串

Question

我遇到了一个问题，要求从左边找到字符数差异最大的最短子串。我们保证该字符串仅包含两个字符，例如“A”和“B”。我们需要找到最短和最左边的子串，使得该子串中 'A' 和 'B' 的计数绝对差值最大。

例如“BAABAABAABB”。在这种情况下，子字符串将是“AABAABAA”，子字符串从索引 1 开始到 8 结束，因为 A 的计数是 6，B 的计数是 2，所以差是 4。所以，答案是 (1, 8)，即子串的起始索引和结束索引。

我用 Python 编写了一个算法，可以按以下方式执行此操作。

max_diff = 0

def calc(word):
    return abs(word.count('A') - word.count('B'))      

def get_window(word):
    if len(word) == 1:
        return (0, 0)
    for start in range(len(word)-1):
        for end in range(start+1, len(word)):
            diff =calc(word[start:end+1])
            if diff == max_diff:
                return (start, end)

word = "BAABAABAABB"
for start in range(len(word)-1):
    for end in range(start+1, len(word)):
        max_diff = max(max_diff, calc(word[start:end+1]))
print get_window(word)

我认为这个解决方案的时间复杂度是 O(N^3)。 我将如何着手提高该程序的效率？可能有更有效和更快的方法来解决这个问题。任何有助于提高效率和提出改进算法的帮助都会非常有帮助。谢谢!

Answer 1

它应该以这种方式工作:

创建第二个数组，代表字符“之间”的数字，例如，A 加一，B 减一。例如，这个数组看起来像

 0 -1  0  1  0  1  2  1  2  3  2  1 
  B  A  A  B  A  A  B  A  A  B  B

在构建数组的过程中，记住值最小和最大的位置。如果有多个最大或最小点，任务现在会减少以找到距离最近的最大和最小点。

为什么会这样？

很容易看出你的calc(word)的结果始终与“包围”此 word 的数组编号的绝对差相同.示例:对于“ABA”calc()将返回 1，如果您查看两次出现的“ABA”的封闭数字，它们是 0 和 1(结果 1)以及 1 和 2(也是结果 1)。

所以calc()的最大可能值对于给定的字符串(这是所需的最大差值)是数组数字的极值的绝对差，只有当具有这些极值的数组索引用于“包围”子字符串时才会出现。

寻找最短的极值距离

假设最大点和最小点现在包含在两个有序列表中l1和 l2 (索引号从小到大)进一步的算法如下:

• (循环开始)
• 确保 l1[0] < l2[0] , 否则交换 l1和 l2
• 记住(l1[0], l2[0], l2[0] - l1[0])作为可能的结果候选人 如果您之前没有遇到更好的候选人。
• 从l1中删除第一个元素.如果l1现在是空的结束循环。
• 返回循环开始。