String and frequency greedy

1record HuffNode(int weight, char symbol, HuffNode left, HuffNode right) {
2    boolean leaf() { return left == null; }
3}
4
5static Map<Character, String> huffman(String text) {
6    Map<Character, Integer> freq = new TreeMap<>();
7    for (char c : text.toCharArray()) freq.merge(c, 1, Integer::sum);
8    PriorityQueue<HuffNode> pq = new PriorityQueue<>(Comparator.comparingInt(HuffNode::weight));
9    for (var e : freq.entrySet()) pq.add(new HuffNode(e.getValue(), e.getKey(), null, null));
10    while (pq.size() > 1) {
11        HuffNode a = pq.poll(), b = pq.poll();                   // the two lightest trees
12        pq.add(new HuffNode(a.weight() + b.weight(), '\0', a, b));
13    }
14    Map<Character, String> codes = new TreeMap<>();
15    if (!pq.isEmpty()) assign(pq.poll(), "", codes);
16    return codes;
17}
18
19static void assign(HuffNode n, String prefix, Map<Character, String> codes) {
20    if (n.leaf()) { codes.put(n.symbol(), prefix.isEmpty() ? "0" : prefix); return; }   // one-symbol text gets code "0"
21    assign(n.left(), prefix + "0", codes);
22    assign(n.right(), prefix + "1", codes);
23}

1static String reorganize(String s) {
2    int[] count = new int[26];
3    for (char c : s.toCharArray()) count[c - 'a']++;
4    PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> y[1] - x[1]);   // {letter, count}, largest count first
5    for (int i = 0; i < 26; i++) if (count[i] > 0) heap.add(new int[]{i, count[i]});
6    StringBuilder sb = new StringBuilder();
7    int[] held = null;                                       // previous letter, kept out of the heap for one step
8    while (!heap.isEmpty()) {
9        int[] cur = heap.poll();
10        sb.append((char) ('a' + cur[0]));
11        cur[1]--;
12        if (held != null) heap.add(held);
13        held = cur[1] > 0 ? cur : null;
14    }
15    return held == null ? sb.toString() : "";              // a letter left over means the input was impossible
16}

1// returns -1 when no palindrome can be formed
2static int minSwapsToPalindrome(String s) {
3    int[] count = new int[256];
4    for (char c : s.toCharArray()) count[c]++;
5    int odd = 0;
6    for (int c : count) odd += c & 1;
7    if (odd > (s.length() & 1)) return -1;
8    char[] a = s.toCharArray();
9    int swaps = 0;
10    for (int i = 0, j = a.length - 1; i < j; i++, j--) {
11        int k = j;
12        while (k > i && a[k] != a[i]) k--;                   // matching character nearest the right end
13        if (k == i) {                                        // a[i] is the odd one out: nudge it toward the centre
14            char t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
15            swaps++;
16            i--; j++;                                        // retry the same pair of positions
17        } else {
18            for (; k < j; k++) { char t = a[k]; a[k] = a[k + 1]; a[k + 1] = t; swaps++; }
19        }
20    }
21    return swaps;
22}

1static String removeKDigits(String num, int k) {
2    StringBuilder stack = new StringBuilder();
3    for (char c : num.toCharArray()) {
4        while (k > 0 && stack.length() > 0 && stack.charAt(stack.length() - 1) > c) {
5            stack.setLength(stack.length() - 1);             // pop a larger digit that precedes a smaller one
6            k--;
7        }
8        stack.append(c);
9    }
10    stack.setLength(Math.max(0, stack.length() - k));        // digits were non-decreasing: remove from the end
11    int start = 0;
12    while (start < stack.length() - 1 && stack.charAt(start) == '0') start++;   // strip leading zeros
13    String result = stack.substring(start);
14    return result.isEmpty() ? "0" : result;
15}