k_distance_group.java

public String sort(String s, int k) {

    Map<Character, Integer> map = new HashMap<>();
    for(char c : s.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }

    // largest char first
    PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((a,b) -> {
        return (b.getKey() - a.getKey());
    });

    pq.addAll(map.entrySet());

    String res = "";
    List<Map.Entry<Character, Integer>> list = new ArrayList<>();
  
    while (!pq.isEmpty()) {

        // this is the left over list
        // if we have any left over, just add the next largest character once
        // and add the leftover back for the next iteration
        if (!list.isEmpty()) {
            Map.Entry<Character, Integer> entry = pq.poll();
            entry.setValue(entry.getValue() - 1);
            res += entry.getKey();

            pq.add(list.get(0));
            list.remove(0);
            pq.add(entry);
            continue;
        }

        Map.Entry<Character, Integer> top = pq.poll();
      
        if (top.getValue() == 0) {
            continue;
        } else if (top.getValue() > k) {
            // if we cannot fit all the characters, then add all of them
            // and stoer the extra chars in "list"
            for (int  i = 0; i <= top.getValue() - k; i ++) {
                res += top.getKey();
            }
            top.setValue(top.getValue() - k);
            list.add(top);
        } else {
            // if we cab fit all the chars, then just add one on the top and add it back for the next iteration
            res += top.getKey();
            top.setValue(top.getValue() - 1);
            pq.add(top);
        }

    }

    return res;
}

@Test
public void tt() {
    String t = "dddccb";
    int k = 2;
    // ddcdcb
    System.out.println(sort(t, k));
}

@Test
public void tt2() {
    String t = "ddd";
    int k = 2;
    // dd
    System.out.println(sort(t, k));
}