基本信息

  • 题号：767
  • 题厂：特斯拉
  • 难度系数：中


已知一个字符串，重新安插字符，要求相同字符不能连在一起，返回该字符。如果满足不了条件，就返回空……

例如：s = "aab"，返回 "aba"；s = "aaab"，返回 ""，因为没有满足的情况


解题思路

  • 为了尽可能满足相同字符不挨在一起，于是考虑从出现频率高的字符开始排
  • 为了让相邻字符不相同，于是问题转换为——如何有效间隔安插。间隔安插问题与 #621 安排任务 似曾相识。在 #621 安排任务 一题我们引入 heap 解决问题，所以本题一样可以引入 heap 帮忙解决问题……
class Solution:
    def reorganizeString(self, s: str) -> str:
        # Counter 捷径：统计字符串各字符出现频率并转化为 hashmap 格式
        count = Counter(s)
        # 初始 maxHeap，元素为 count ～ 字符，heapify 时自动根据 count 排序
        maxHeap = [[-cnt, char] for char, cnt in count.items()]
        heapq.heapify(maxHeap)
        
        # 为了间隔安插，我们需要知道当前字符的前一个字符是啥，于是初始化 prev 为空
        prev = None
        res = ""
        while maxHeap or prev:
            # 安插字符时，maxHeap 为空而 prev 还有元素，说明没有可用字符但还有等待间隔安插的字符——所以该字符满足不了间隔的题目要求，提前返回……
            if prev and not maxHeap:
                return ""
            
            cnt, char = heapq.heappop(maxHeap)
            res += char
            # maxHeap pop 一个字符后，说明已经安排了一个与 prev 值不同的字符，这时 prev 可以放回 maxHeap 循环；
            # 与此同时 prev 也需要重设一下……
            if prev:
                heapq.heappush(maxHeap, prev)
                prev = None
            # 更新 maxHeap 刚刚 pop 的元素 count：count 为 0 说明该元素已经完成安插可以销毁；count 不为 0 需要放入刚刚清空的 prev 等待时机重回 maxHeap 被安排……    
            cnt += 1
            if cnt:
                prev = [cnt, char]
                
        return res


Constraints

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.


Big O

  • Time：O（ n * logn ）做了一遍循环 O（n），每次遍历时 maxHeap 需要整理一次 O（logn）
  • Space：O（26），字符串由 26 个小写英文字母组成，maxHeap 的长度最多为 26



测试

  • 当 s 无法满足相邻字符不相同时
  • 当 s 满足时
  • s 长度为 1 的边缘案例时……
  • ……


总结

  • 本题和 #621 安排任务 极其相似，本题可与 #621配套复习，理解 heap 解决间隔安排问题的原理和逻辑思路……