A和B计数差异最大的最短的子串
我遇到了一个问题，要求从左边开始查找字符计数差异最大的最短的子字符串。我们保证字符串只包含两个字符，比如'A‘和'B’。我们需要找到最短和最左边的子串，使该子串中'A‘和'B’的计数的绝对差值最大化。
例如"BAABAABAABB“。在这种情况下，子串将是"AABAABAA"，子串从索引1开始，结束于8，因为A的计数是6，B是2，因此，答案将是(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)。我该如何着手提高这个程序的效率呢？可能会有更有效和更快的方法来解决这个问题。任何有助于提高效率并提出改进算法的方法都将非常有帮助。谢谢!
回答 1
Stack Overflow用户
发布于 2017-11-12 09:52:52
它应该是这样工作的：
创建第二个数组，表示字符之间的数字，例如，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 (从最小索引号到最大索引号)中，则进一步的算法如下：
如果你没有遇到一个更好的候选before.
- Remove
- before.
- Remove
l1[0] < l2[0]，那么就把l1和(l1[0], l2[0], l2[0] - l1[0])互换为可能的候选结果。如果l1为空，则立即结束循环。- 返回到循环开始。
https://stackoverflow.com/questions/47244596
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号