#767 Reorganize String

1class Solution {2    public String reorganizeString(String s) {3        int[] count = new int[26];4        for (char c : s.toCharArray()) count[c - 'a']++;5        // max-heap of letters by remaining count6        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> Integer.compare(count[b], count[a]));7        for (int c = 0; c < 26; c++) if (count[c] > 0) heap.offer(c);8        StringBuilder sb = new StringBuilder();9        int held = -1;                                   // letter we just used: must sit out one turn10        while (!heap.isEmpty()) {11            int c = heap.poll();                         // most frequent letter that isn't the last one12            sb.append((char) ('a' + c));13            count[c]--;14            if (held >= 0 && count[held] > 0) heap.offer(held);   // previous letter may come back now15            held = c;16        }17        return sb.length() == s.length() ? sb.toString() : "";   // stuck with only `held` left → impossible18    }19}

1class Solution {2    public String reorganizeString(String s) {3        int n = s.length();4        int[] count = new int[26];5        int top = 0;6        for (char c : s.toCharArray()) if (++count[c - 'a'] > count[top]) top = c - 'a';7        if (count[top] > (n + 1) / 2) return "";        // too many of one letter: impossible8        char[] out = new char[n];9        int i = 0;10        for (; count[top] > 0; count[top]--, i += 2) out[i] = (char) ('a' + top);   // most frequent first11        for (int c = 0; c < 26; c++) {12            for (; count[c] > 0; count[c]--, i += 2) {13                if (i >= n) i = 1;                       // even slots full → switch to odd slots14                out[i] = (char) ('a' + c);15            }16        }17        return new String(out);18    }19}