358. Rearrange String k Distance Apart

Rearrange String k Distance Apart

Given a non-empty string s 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:

s = "aabbcc", k = 3

Result: "abcabc"

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

Example 2:

s = "aaabc", k = 3

Answer: ""

It is not possible to rearrange the string.

Example 3:

s = "aaadbbcc", k = 2

Answer: "abacabcd"

Another possible answer is: "abcabcda"

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

Credits:Special thanks to @elmirap for adding this problem and creating all test cases.

Solution

public class Solution {

    public String rearrangeString(String str, int k) {
        Map<Character, Integer> map = new HashMap<>();
        for (Character c : str.toCharArray()) {
            map.merge(c, 1, (a, b) -> a + b);
        }

        List<Result> results = new ArrayList<>();
        for (Character c : map.keySet()) {
            results.add(new Result(c, map.get(c)));
        }

        Collections.sort(results, (a, b) -> b.count - a.count);

        // check k one by one
        int size = str.length();
        int count = results.get(0).count;
        if ((count - 1) * k + 1 > size) {
            return "";
        }

        size -= count;
        List<StringBuffer> buckets = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            buckets.add(new StringBuffer().append(results.get(0).ch));
        }

        k -= 1;

        int runner = 0;
        for (int i = 1; i < results.size(); i++) {

            if (count != results.get(i).count) {
                runner = 0;
            }

            count = results.get(i).count;
            if ((count - 1) * k + 1 > size) {
                return "";
            }

            for (int j = 0; j < count; j++) {
                buckets.get(runner).append(results.get(i).ch);
                runner += 1;
                runner %= buckets.size();
            }
            k -= 1;
            size -= count;
        }

        return buckets.stream().reduce(new StringBuffer(), (a, b) -> {
            a.append(b);
            return a;
        }).toString();
    }

    private class Result {
        char ch;
        int count;

        public Result(char ch, int count) {
            this.ch = ch;
            this.count = count;
        }
    }



}