3

这是 来自spoj 的一个问题

给出一个由 N 个英文字母（'a'-'z'）的小写字母组成的单词。我们想选择单词的一个非空的连续（即一个片段）片段，以使片段中出现频率最高和最不频繁的字母出现次数的差异最大化。我们假设最不频繁的字母必须在结果片段中至少出现一次。特别是，如果片段只包含一个字母，那么其中出现频率最高的字母和频率最低的字母就会重合。

例子：

输入

  • 10
  • 啊啊啊啊

输出

  • 3

如果只有两个字母（比如 a 和 b）
1）计数器初始化为零，我有一种方法。
2) 现在从左到右遍历字符串，每次出现a递增计数器，每次出现b递减计数器。
3) 计数器最大值和最小值的绝对差值给出解。

现在我可以通过检查每一对a&来扩展这种方法，b这使得我的算法运行时间 26 * 26 * length of string。我应该注意我得到一个单独只有一个字符的子字符串的情况。但是这种运行对于当前的问题是不够的。如何优化我的算法或有更好的算法？

4

1 回答 1

1

一个小的优化是在单次遍历字符串期间跟踪所有 26*26 计数器（每对字母 1 个）。

这样做的好处是，当你读取字符时，你只需要更新对应字母的对。

换句话说，您正在更新 26*2 计数器而不是 26*26，因此运行时间更像是 2 * 26 * 字符串长度。

另一个可能的优化是，如果 a < b，您可以通过仅跟踪对 a 和 b 来减少计数器的数量。b,a 的计数器将始终是 a,b 的计数器的负数。

总的来说，我希望这两个更改可以将您的运行时间减少大约 26 倍。

于 2013-11-08T08:37:39.657 回答