767. 重构字符串

问题描述

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

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

示例 1:

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

示例 2:

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

注意:

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

解题思路

当满足下列条件时，一定可以得到两相邻的字符不同的字符串：

1. 当 \(S\) 的长度 \(n\) 为奇数时，出现的最多的字符的次数不超过 \(n//2+1\).
2. 当 \(S\) 的长度 \(n\) 为偶数时，出现的最多的字符的次数不超过 \(n//2\).

综合来说，只要出现的最多的字符的次数不超过 \((n+1)//2\) 就可以得到两相邻的字符不同的字符串。

---

from collections import Counter

class Solution:
    def reorganizeString(self, S: str) -> str:
        count = Counter(S).most_common()
        n = len(S)
        if count[0][1] > (n + 1) // 2:
            return ""
        p = []
        for c, t in count:
            p.append(c * t)
        q = "".join(p)
        ans = [""] * n
        ans[::2] = q[: (n + 1) // 2]
        ans[1::2] = q[(n + 1) // 2 :]
        return "".join(ans)

返回顶部

在手机上阅读