public String reorganizeString(String S) {

int[] hash = new int[26];

for(char c : S.toCharArray()) hash[c-'a']++;

int max = 0;

for(int i = 0; i<26; ++i){

if(hash[i] > hash[max]) max = i;

}

if(hash[max] > (S.length()+1)/2) return "";

char[] res = new char[S.length()];

int ptr = 0;

while(hash[max]-- > 0){

res[ptr] = (char)(max + 'a');

ptr += 2;

}

for(int i = 0; i<26; ++i){

while(hash[i]-- > 0){

if(ptr >= S.length()) ptr = 1;

res[ptr] = (char)(i + 'a');

ptr += 2;

}

}

return new String(res);

}

/**

public String reorganizeString2(String S) {

int N = S.length();

int[] count = new int[26];

for (char c: S.toCharArray()) count[c-'a']++;

PriorityQueue<MultiChar> pq = new PriorityQueue<MultiChar>((a, b) ->

a.count == b.count ? a.letter - b.letter : b.count - a.count);

for (int i = 0; i < 26; ++i) if (count[i] > 0) {

if (count[i] > (N + 1) / 2) return "";

pq.add(new MultiChar(count[i], (char) ('a' + i)));

}

StringBuilder ans = new StringBuilder();

while (pq.size() >= 2) {

MultiChar mc1 = pq.poll();

MultiChar mc2 = pq.poll();

/*This code turns out to be superfluous, but explains what is happening

ans.append(mc1.letter);

ans.append(mc2.letter);

if (--mc1.count > 0) pq.add(mc1);

if (--mc2.count > 0) pq.add(mc2);

}

if (pq.size() > 0) ans.append(pq.poll().letter);

return ans.toString();

}

class MultiChar {

int count;

char letter;

MultiChar(int ct, char ch) {

count = ct;

letter = ch;

}

}

// use 358. Rearrange String k Distance Apart

public String reorganizeString3(String S) {

return rearrangeString(S, 2);

}

public String rearrangeString(String str, int k) {

int length = str.length();

int[] count = new int[26];

int[] nextIndex = new int[26];

char[] chars = str.toCharArray();

for (char ch: chars){

count[ch-'a']++;

}

StringBuilder sb = new StringBuilder();

for (int i=0; i<length; i++) {

int idx = findValidMax(count, nextIndex, i);

if (idx == -1) return "";

sb.append((char) (idx + 'a'));

count[idx]--;

nextIndex[idx] = i+k;

}

return sb.toString();

}

private int findValidMax(int[] count, int[] nextIndex, int index){

int max = Integer.MIN_VALUE;

int idx = -1;

for (int i=0; i<26; i++) {

if (count[i] != 0 && count[i] > max && index >= nextIndex[i]) {

max = count[i];

idx = i;

}

}

return idx;

}

/**

public String reorganizeString4(String S) {

int n = S.length();

int[] cnt = new int[128];

char mc = 'a';

for (char c : S.toCharArray()) {

cnt[c]++;

mc = (cnt[c] > cnt[mc]) ? c : mc;

}

if (cnt[mc] == 1) {

return S;

}

if (n - cnt[mc] <= cnt[mc] - 2) {

return "";

}

StringBuilder[] sb = new StringBuilder[cnt[mc]];

for (int i = 0; i < sb.length; i ++) {

sb[i] = new StringBuilder();

sb[i].append(mc);

}

int k = 0;

for (char c = 'a'; c <= 'z'; c++) {

while (c != mc && cnt[c] > 0) {

sb[k++].append(c);

cnt[c]--;

k %= sb.length;

}

}

for (int i = 1; i < sb.length; i++) {

sb[0].append(sb[i]);

}

return sb[0].toString();

}