daily_leetcode_2020_1130_767_重构字符串

1 题目描述

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

若可行，输出任意可行的结果。若不可行，返回空字符串
S 只包含小写字母并且长度在[1, 500]区间内。

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

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

2 题解

参考题解，作者：sdwwld

原处讲解的非常清楚。

大概说一下思路：

从原始串中找出出现次数最多的字符highest_freq_char，如果出现的最高频率有： max_freq > (s_len + 1) >> 1,则不能构成，将highest_freq_char存放在偶数位，然后再将其他字符存放在没有放的位置(包括没有放highest_freq_char的偶数位，奇数位)

    def reorganizeString(self, S: str) -> str:

        s_len = len(S)
        hash_list = [0] * 26
        threshold = (s_len + 1) >> 1  # 阈值，出现次数最多的元的临界值
        base_val = ord('a')

        # 做hash映射，并寻找出现次数最多的元
        highest_freq_char = None
        max_freq = 0

        for ch in S:
            hash_list[ord(ch) - base_val] += 1
            if hash_list[ord(ch) - base_val] > max_freq:
                max_freq = hash_list[ord(ch) - base_val]
                highest_freq_char = ch
                # 超过阈值，则不能构成要求的串
                if max_freq > threshold:
                    return ""

        # 将出现最多的元放在偶数位
        res = [""] * s_len
        index = 0
        while hash_list[ord(highest_freq_char) - base_val]:
            res[index] = highest_freq_char
            index += 2
            hash_list[ord(highest_freq_char) - base_val] -= 1

        # 将其他元放在剩下的位置上
        for ch in S:
            # ch有时 且 不为最多串 时 放
            if hash_list[ord(ch) - base_val] and ch != highest_freq_char:
                while hash_list[ord(ch) - base_val]:
                    if index >= s_len:
                        index = 1
                    res[index] = ch
                    index += 2
                    hash_list[ord(ch) - base_val] -= 1

        return ''.join(res)