# Rearrange String k Distance Apart

This page explains Java solution to problem `Rearrange String k Distance Apart` using `Priority Queue` data structure.

## Problem Statement

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:

Input: s = "aabbcc", k = 3
Output:"abcabc"
Explanation: The same letters are at least distance 3 from each other.

Example 2:

Input: s = "aaabc", k = 3
Output: ""
Explanation: It is not possible to rearrange the string.

Example 3:

Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Explanation: The same letters are at least distance 2 from each other.

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class RearrangeStringKDistanceApart {
static class Entry {
char ch;
int count;

Entry(char ch, int count) {
this.ch = ch;
this.count = count;
}
}
public String rearrangeString(String s, int k) {
HashMap<Character, Integer> map = new HashMap<>();
for(int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
map.put(ch, map.getOrDefault(ch, 0) + 1);
}

PriorityQueue<Entry> pq = new PriorityQueue<Entry>(new Comparator<Entry>(){
public int compare(Entry e1, Entry e2) {
int cmp = Integer.compare(e2.count, e1.count);
if(cmp == 0) return e1.ch - e2.ch;
else return cmp;
}
});

for(Map.Entry<Character, Integer> entry: map.entrySet()) {
char ch = entry.getKey();
int count = entry.getValue();
pq.offer(new Entry(ch, count));
}

StringBuilder st = new StringBuilder();
while(!pq.isEmpty()) {
Entry e = pq.poll();
st.append(e.ch);
q.offer(new Entry(e.ch, e.count - 1));
if(q.size() >= k) {
Entry eNew = q.poll();
if(eNew.count > 0) pq.offer(eNew);
}
}
return st.length() == s.length() ? st.toString() : "";
}
}
``````

## Time Complexity

O(N log N) Where
N is total number of elements in an input string

## Space Complexity

O(N + K) Where
N is total number of elements in an input string
K is same character distance from each other