358. Rearrange String k Distance Apart

Given a non-empty string str and an integer k, rearrange the string such that the same characters are at least distance k from each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".

Example 1: str = "aabbcc", k = 3

Result: "abcabc"

The same letters are at least distance 3 from each other. Example 2: str = "aaabc", k = 3

Answer: ""

It is not possible to rearrange the string. Example 3: str = "aaadbbcc", k = 2

Answer: "abacabcd"

Another possible answer is: "abcabcda"

The same letters are at least distance 2 from each other.

This question is tricky, not only need you process the string tally the number, then you need to use heap to pull char out, and in a defined sequence.

public class Solution {
    public String rearrangeString(String str, int k) {

        if(k == 0) return str;

        int len = str.length();
        Map<Character, Integer> counts = new HashMap<>();
        for(int i=0; i< len; i++){
            char ch = str.charAt(i);
            int n =1;
                n = counts.get(ch)+1;
            counts.put(ch, n);

        PriorityQueue<Pair> pq = new PriorityQueue<>(10, new Comparator<Pair>(){
            public int compare(Pair p1, Pair p2){
                if(p1.cnt != p2.cnt) return p2.cnt - p1.cnt;
                else return  p2.ch - p1.ch; // to ensure the order of the chars with same count, they should show up in same order.

        for(Map.Entry<Character, Integer> entry : counts.entrySet()){
            pq.offer(new Pair(entry.getKey(), entry.getValue()));// pick the most show-up char first.

        StringBuilder sb = new StringBuilder();
            List<Pair> tmp = new ArrayList<>();// this is avoid you pick up same char in the same k-segment.
            int d = Math.min(k, len);
            for(int i=0; i< d; i++){
                if(pq.isEmpty()) return "";
                Pair p = pq.poll();
                if(--p.cnt > 0) tmp.add(p);
            for(Pair p : tmp) pq.offer(p);


        return sb.toString();


    class Pair{
        char ch;
        int cnt;
        Pair(char c, int t){
            ch = c;
            cnt = t;

results matching ""

    No results matching ""