Reorganize String

1package pkg5leetcode.interview150;2 3/*4 * Reorganize String | LC 7675 * APPROACH: Max heap by frequency; place most frequent with gap.6 * COMPLEXITY: Time O(n log k), Space O(k)7 */8import java.util.*;9 10public class interview150_LC767ReorganizeString {11    static String reorganizeString(String s) {12        int[] cnt = new int[26];13        for (char c : s.toCharArray()) cnt[c - 'a']++;14        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);15        for (int i = 0; i < 26; i++) if (cnt[i] > 0) pq.offer(new int[]{i, cnt[i]});16        StringBuilder sb = new StringBuilder();17        while (!pq.isEmpty()) {18            int[] a = pq.poll();19            if (sb.length() > 0 && sb.charAt(sb.length() - 1) == (char) ('a' + a[0])) {20                if (pq.isEmpty()) return "";21                int[] b = pq.poll();22                sb.append((char) ('a' + b[0]));23                if (--b[1] > 0) pq.offer(b);24                pq.offer(a);25            } else {26                sb.append((char) ('a' + a[0]));27                if (--a[1] > 0) pq.offer(a);28            }29        }30        return sb.toString();31    }32 33    public static void main(String[] args) {34        check(reorganizeString("aab").equals("aba"), "case1");35        check(reorganizeString("aaab").equals(""), "case2");36        System.out.println("all tests passed");37    }38 39    static void check(boolean cond, String name) {40        if (!cond) throw new AssertionError("FAILED: " + name);41        System.out.println("  PASS " + name);42    }43}