Leetcode 767. 重构字符串

小咪咪 2022-09-16 11:10 94阅读 0赞

## 题目重述 ##

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

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

### 示例 1: ###

输入: S = “aab”  
输出: “aba”

### 示例 2: ###

输入: S = “aaab”  
输出: “”  
注意:

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/reorganize-string  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 思路 ##

优先级队列

## Java实现 ##

class Solution {
        
        public String reorganizeString(String s) {
        
            Map<Character,Integer> m = new HashMap<>();
            int maxCount = 0;
            for (int i = 0; i < s.length(); i++) {
        
                int cnt = m.getOrDefault(s.charAt(i),0)+1;
                m.put(s.charAt(i),cnt);
                maxCount = Math.max(maxCount,cnt);
            }
            //  大于二分之一长度 必不可行
            if ( maxCount > (s.length() + 1) / 2) {
        
                return "";
            }
            Queue<Character> queue = new PriorityQueue<>(new Comparator<Character>() {
        
                @Override
                public int compare(Character o1, Character o2) {
        
                    return m.getOrDefault(o2,0)-m.getOrDefault(o1,0);
                }
            });
            for (Character c : m.keySet()){
        
                queue.add(c);
            }
            StringBuilder sb = new StringBuilder();
            while(queue.size()>1){
        
                Character c1 = queue.poll();
                Character c2 = queue.poll();
                sb.append(c1);
                sb.append(c2);
                m.put(c1,m.get(c1)-1);
                m.put(c2,m.get(c2)-1);
                if(m.get(c1)>0){
        
                    queue.add(c1);
                }
                if(m.get(c2)>0){
        
                    queue.add(c2);
                }
                if(queue.size()==1){
        
                    sb.append(queue.poll());
                }
            }
            return sb.toString();
        }
    }