How to randomly permutate string without adjacent equal elements

So, I have an example string like "aaabbbc", i would like to shuffle it randomly but no two consecutive letters should be same in the result. The output should be "abababc" or "cbababa" or "abacbab" etc.

I've tried a code using PriorityQueue, its solve the problem, but only one way not randomly generate many ways to shuffle my string with no two consecutive. Below is code that i've used.

    int n = str.length();
    int[] count = new int[MAX_CHAR];

    for (int i = 0; i < n; i++) {
        count[str.charAt(i) - 'a']++;
    }

    PriorityQueue<Key> pq = new PriorityQueue<>(new KeyComparator());
    for (char c = 'a'; c <= 'z'; c++) {
        int val = c - 'a';
        if (count[val] > 0) {
            pq.add(new Key(count[val], c));
        }
    }
    str = "";

    Key prev = new Key(-1, '#');
    while (pq.size() != 0) {
        Key k = pq.peek();
        pq.poll();
        str = str + k.ch;

        if (prev.freq > 0) {
            pq.add(prev);
        }

        (k.freq)--;
        prev = k;
    }

    if (n != str.length()) {
        return "";
    } else {
        return str;
    }

I am stuck when trying to make it randomly by that algorithm. The result i wanted is dynamic output like i described above. Thanks