贪心算法（19）（java）重构字符串

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

返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。

示例 1:

输入: s = "aab"
输出: "aba"

示例 2:

输入: s = "aaab"
输出: ""

public class Solution {public String reorganizeString(String s) {int[] hash=new int[26];char maxChar=' ';int maxCount=0;for (int i=0;i<s.length();i++){char ch=s.charAt(i);if (maxCount<++hash[ch-'a']){maxChar=ch;maxCount=hash[ch-'a'];}}int n=s.length();//先判断if (maxCount>(n+1)/2)return "";char[] ret=new char[n];int index=0;//先处理次数最多的字符for (int i=0;i<maxCount;i++){ret[index]=maxChar;index+=2;}hash[maxChar-'a']=0;for (int i=0;i<26;i++){for (int j=0;j<hash[i];j++){if (index>=n)index=1;ret[index]=(char)(i+'a');index +=2;}}return  new String(ret);}public static void main(String[] args) {Solution solution=new Solution();String input="aaab";String output=solution.reorganizeString(input);System.out.println("输出:\""+output+"\"");}
}