0767. Reorganize String¶
题目信息¶
- 题号:
0767
- 难度:
Medium
- 主题:
字符串、字符重排、相邻约束
- 原题:
- 重点:
必须保留原字符串中每个字符的出现次数,并使任意两个相邻字符不同;存在多种答案时任意一种均可,不可能时返回空字符串
题目重述¶
给定一个只含小写英文字母的字符串 s。请重新排列其中的全部字符,使结果中任意两个相邻位置的字符都不相同。每个字符必须按其在原字符串中的出现次数完整保留,不能添加或删除字符。
若存在多个合法排列,可以返回任意一个;若无法满足相邻字符不同的要求,返回空字符串 ""。1 <= s.length <= 500。
自建示例¶
存在多种合法排列:
输入:s = "aaabbc"
输出:"ababac"
解释:结果仍包含三个 a、两个 b 和一个 c,并且相邻字符均不相同;其他满足相同条件的排列也合法。
最高频字符无法被隔开:
输入:s = "bbbbac"
输出:""
解释:四个 b 之间至少需要三个非 b 字符才能全部隔开,但字符串中只有 a、c 两个非 b 字符,因此不存在合法排列。