0767. Reorganize String

题目信息

题号:

0767

难度:

Medium

主题:

字符串、字符重排、相邻约束

原题:

LeetCode 0767

重点:

必须保留原字符串中每个字符的出现次数,并使任意两个相邻字符不同;存在多种答案时任意一种均可,不可能时返回空字符串

题目重述

给定一个只含小写英文字母的字符串 s。请重新排列其中的全部字符,使结果中任意两个相邻位置的字符都不相同。每个字符必须按其在原字符串中的出现次数完整保留,不能添加或删除字符。

若存在多个合法排列,可以返回任意一个;若无法满足相邻字符不同的要求,返回空字符串 ""。1 <= s.length <= 500。

自建示例

存在多种合法排列:

输入:s = "aaabbc"
输出:"ababac"
解释:结果仍包含三个 a、两个 b 和一个 c,并且相邻字符均不相同;其他满足相同条件的排列也合法。

最高频字符无法被隔开:

输入:s = "bbbbac"
输出:""
解释:四个 b 之间至少需要三个非 b 字符才能全部隔开,但字符串中只有 a、c 两个非 b 字符,因此不存在合法排列。