https://leetcode.com/problems/reorganize-string/

Solution.java

class Solution {
    public String reorganizeString(String S) {
        Character[] c = new Character[S.length()];
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0;i<S.length();i++) {
            c[i] = S.charAt(i);
            map.putIfAbsent(S.charAt(i), 0);
            map.put(S.charAt(i), map.get(S.charAt(i))+1);
        }
        Arrays.sort(c, new Comparator<Character>(){
            public int compare(Character c1, Character c2) {
                int v1 = map.get(c1);
                int v2 = map.get(c2);
                if(v1 == v2) {
                    return c2 - c1;
                } else {
                    return v2 - v1;
                }
            }
        });
        
        StringBuilder sb = new StringBuilder();
        int start = 0;
        int end = c.length-1;
        int count = 0;
        while(start<end) {
            sb.append(c[start++]).append(c[end--]);
            count+=2;
        }
        if(count<c.length) sb.append(c[start++]);
        for(int i = 1; i<sb.toString().length()-1;i++) {
            if(sb.charAt(i) == sb.charAt(i-1) || sb.charAt(i)==sb.charAt(i+1)) return "";
        }
        return sb.toString();
    }
}