重构字符串
Reorganize String
题目详情
问题：重构字符串
考察：字符串、贪心、栈
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/reorganize-string/
Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
Return any possible rearrangement of s or return "" if not possible.
Example 1:
Input: s = "aab" Output: "aba"
Example 2:
Input: s = "aaab" Output: ""
Constraints:
1 <= s.length <= 500sconsists of lowercase English letters.
解析
思路：统计字符频次，每次取剩余次数最多且不同于上一个字符的字符放入结果。可用最大堆，也可先判断最大频次是否超过 (n+1)/2。
复杂度：堆解法 O(n log A)，A 为字符种类数；空间 O(A)。