# 358 Rearrange String k Distance Apart

### Problem:

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

It is not possible to rearrange the string.
``````

Example 3:

``````s = "aaadbbcc", k = 2

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

### Solutions:

``````public class Solution {
private class Node implements Comparable<Node>{
public char c;
public int count;
public Node(char c, int count) {
this.c = c;
this.count = count;
}
public int compareTo(Node n) {
return n.count - this.count;
}
}
public String rearrangeString(String s, int k) {
PriorityQueue<Node> q = new PriorityQueue<Node>();
int[] valid = new int[26];
int[] count = new int[26];
for (int i = 0; i < s.length() ; i ++) {
count[s.charAt(i) - 'a'] ++;
}
for (int i = 0; i < 26; i ++) {
if (count[i] != 0) {
}
}
StringBuilder sb = new StringBuilder();
int index = 0;
while (!q.isEmpty()) {
Stack<Node> tmp = new Stack<Node>();
while (!q.isEmpty() && index < valid[q.peek().c - 'a']) {
tmp.push(q.poll());
}
if (q.isEmpty()) {
return "";
}
Node n = q.poll();
char c = n.c;
if (n.count > 1) {
}
while (!tmp.isEmpty()) {
}
valid[c - 'a'] = index + k;
sb.append(c);
index ++;
}
return sb.toString();
}
}
``````
``````public class Solution {
public String rearrangeString(String s, int k) {
if (k == 0) {
return s;
}
int[] count = new int[26];
for(int i=0; i < s.length(); i++){
count[s.charAt(i) - 'a'] ++;
}
PriorityQueue<Character> q = new PriorityQueue<Character>(new Comparator<Character>(){
public int compare(Character c1, Character c2){
if (count[c1 - 'a'] != count[c2 - 'a']) {
return count[c2 - 'a'] - count[c1 - 'a'];
}
else {
return c1 - c2;
}
}
});

for (int i = 0; i < 26; i ++) {
if (count[i] != 0) {
}
}
StringBuilder sb = new StringBuilder();
int len = s.length();
while(!q.isEmpty()){
int cnt = Math.min(k, len);
ArrayList<Character> tmp = new ArrayList<Character>();
for(int i=0; i < cnt; i++){
if(q.isEmpty())
return "";
char c = q.poll();
sb.append(c);
count[c - 'a'] --;
if(count[c - 'a'] > 0){
}
len--;
}

for(char c: tmp)