leetcode常规算法题复盘（第八期）—

leetcode常规算法题复盘（第八期）——重构字符串

题目原文

767. 重构字符串

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab"
输出: "aba"

示例 2:

输入: S = "aaab"
输出: ""

注意:

S 只包含小写字母并且长度在[1, 500]区间内。

标准题解

最大堆：

 1 class Solution:
 2     def reorganizeString(self, S: str) -> str:
 3         if len(S) < 2:
 4             return S
 5         
 6         length = len(S)
 7         counts = collections.Counter(S)
 8         maxCount = max(counts.items(), key=lambda x: x[1])[1]
 9         if maxCount > (length + 1) // 2:
10             return ""
11         
12         queue = [(-x[1], x[0]) for x in counts.items()]
13         heapq.heapify(queue)
14         ans = list()
15 
16         while len(queue) > 1:
17             _, letter1 = heapq.heappop(queue)
18             _, letter2 = heapq.heappop(queue)
19             ans.extend([letter1, letter2])
20             counts[letter1] -= 1
21             counts[letter2] -= 1
22             if counts[letter1] > 0:
23                 heapq.heappush(queue, (-counts[letter1], letter1))
24             if counts[letter2] > 0:
25                 heapq.heappush(queue, (-counts[letter2], letter2))
26         
27         if queue:
28             ans.append(queue[0][1])
29         
30         return "".join(ans)
31 
32 
33 #作者：LeetCode-Solution
34 #链接：https://leetcode-cn.com/problems/reorganize-string/solution/zhong-gou-zi-fu-chuan-by-leetcode-solution/
35 #来源：力扣（LeetCode）
36 #著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

计数

 1 class Solution:
 2     def reorganizeString(self, S: str) -> str:
 3         if len(S) < 2:
 4             return S
 5         
 6         length = len(S)
 7         counts = collections.Counter(S)
 8         maxCount = max(counts.items(), key=lambda x: x[1])[1]
 9         if maxCount > (length + 1) // 2:
10             return ""
11         
12         reorganizeArray = [""] * length
13         evenIndex, oddIndex = 0, 1
14         halfLength = length // 2
15 
16         for c, count in counts.items():
17             while count > 0 and count <= halfLength and oddIndex < length:
18                 reorganizeArray[oddIndex] = c
19                 count -= 1
20                 oddIndex += 2
21             while count > 0:
22                 reorganizeArray[evenIndex] = c
23                 count -= 1
24                 evenIndex += 2
25         
26         return "".join(reorganizeArray)
27 
28 
29 #作者：LeetCode-Solution
30 #链接：https://leetcode-cn.com/problems/reorganize-string/solution/zhong-gou-zi-fu-chuan-by-leetcode-solution/
31 #来源：力扣（LeetCode）
32 #著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析

    时间复杂度：O(n+∣Σ∣)O(n+|Sigma|)O(n+∣Σ∣)，其中 nnn 是字符串的长度，ΣSigmaΣ 是字符集，在本题中字符集为所有小写字母，∣Σ∣=26|Sigma|=26∣Σ∣=26。
    遍历字符串并统计每个字母的出现次数，时间复杂度是 O(n)O(n)O(n)。
    重构字符串需要进行 nnn 次放置字母的操作，并遍历每个字母得到出现次数，时间复杂度是 O(n+∣Σ∣)O(n+|Sigma|)O(n+∣Σ∣)。
    总时间复杂度是 O(n+∣Σ∣)O(n+|Sigma|)O(n+∣Σ∣)。

    空间复杂度：O(∣Σ∣)O(|Sigma|)O(∣Σ∣)，其中 nnn 是字符串的长度，ΣSigmaΣ 是字符集，在本题中字符集为所有小写字母，∣Σ∣=26|Sigma|=26∣Σ∣=26。这里不计算存储最终答案字符串需要的空间（以及由于语言特性，在构造字符串时需要的额外缓存空间），空间复杂度主要取决于统计每个字母出现次数的数组和优先队列。空间复杂度主要取决于统计每个字母出现次数的数组。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/reorganize-string/solution/zhong-gou-zi-fu-chuan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。