字符串中交替字符的最长子串

Question

我一直在解决这个分而治之的问题，给定一个由小写字符组成的字符串，找到由连续的{辅音，元音}组成的最长子字符串及其在字符串中的位置。

示例。

string = "ehbabebaehehehbe"

solution = "babeba" 位置：3

我尝试了很多东西，发现了这些问题。

我不知道在哪里拆分问题，因为我可能会拆分解决方案，并合并子解决方案，解决方案可能会消失
合并子解决方案时，我不知道是应该合并它们还是选择其中一个，因为我不知道它们是否连续

Answer 1

我已经给了你一些时间来解决你的问题。我想出了一个算法。详情如下。

概念

我们将使用两种方法：

1: int[] maxSubstringOfAlternatingCharacters(String string, int low, int high)

在这个方法中，我们简单地将字符串分成两部分。我们将从中间 开始分割字符串。此方法 returns 一个数组 {startIndex, substringLength}.

2: int[] maxCrossingSubstring(String string, int low, int mid, int high)

在这个方法中，我们找到最大长度的子串，其字符在低位和高位之间交替。此方法 returns 一个数组 {startIndex, substringLength}.

算法

方法一：

1:  int[] maxSubstringOfAlternatingCharacters(String string, int low, int high)
2:
3:      if (low == high) return {low, 1}
4:      
5:      mid = (low + high)/2
6:      leftSubstring = maxSubstringOfAlternatingCharacters(string, low, mid)
7:      rightSubstring = maxSubstringOfAlternatingCharacters(string, mid+1, high)
8:      crossingSubstring = maxCrossingSubstring (string, low, mid, high)
9:
10:     if leftSubstring[1] >= rightSubstring[1] and leftSubstring[1] >= crossingSubstring[1]
11:         return leftSubstring
12:     else if rightSubstring[1] >= leftSubstring[1] and rightSubstring[1] >= crossingSubstring[1]
13:         return rightSubstring
14:     else
15:         return crossingSubstring

方法二：

1:  int[] maxCrossingSubstring (String string, int low, int mid, int high)
2:
3:      if char[mid] and char[mid+1] are not alternating characters
4:          return {low, 0};
5:
6:      leftMaxSubstring = 1;
7:      //Loop from mid to low to find leftMaxSubstring of alternating characters*/
8:      rightMaxSubstring = 1;
9:      //Loop from mid+1 to high to find rightMaxSubstring of alternating characters*/
10:     return {mid-leftMaxSubstring+1, leftMaxSubstring+rightMaxSubstring}

时间复杂度

分割步骤需要O(1)时间。 组合步骤，即找到最大交叉子串最多需要 O(n) 时间，其中 n 是 high-low+1。

递归关系将是：

T(n) = 2T(n/2) + O(n)

这导致时间复杂度为 O(n*logn)。

最后的想法

我没有提供 maxCrossingSubstring 方法的完整实现。 你应该尝试自己做。有什么问题可以评论，我也会补全。如果您在理解算法的任何部分时遇到任何问题，请发表评论，我会更新我的答案以帮助您。

我认为可能会有更快的算法来解决您的问题，它将运行 in O(n)。它将类似于 Kadane's algorithm，因此它将 而不是 是 分而治之算法 。

希望对您有所帮助。 我确实自己实现了这个算法，它对我来说确实适用于许多输入。如果有人发现它有什么问题。发表评论。

字符串中交替字符的最长子串

Longest substring of alternating characters in a string

algorithm

recursion

search

divide-and-conquer

概念

算法

时间复杂度

最后的想法