Skip to content

Latest commit

 

History

History

767.Reorganize-String

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

767.Reorganize-String

本题本质上就是 358. Rearrange String k Distance Apart 当k=2时的特例。

基本的思想就是尽量使用当前频次最多的两个字母。如果不优先使用频次最多的字母,则手头该字母会越积越多。当最终手头只剩一种字母时,构造就会失败。

数据结构上,维护一个优先队列来实时得到当前频次最多的两个字母。只要每次能取两个不同字母组成一对加入字符串,可以保证顺利构造结果。记得使用完之后,将这两种字母频次减一之后再放入队列之中。

失败的条件:队列中只有一种字母,并且字母的频次大于等于2.