Rearrange String k Distance Apart
358. 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.
public class Solution {
public String rearrangeString(String s, int k) {
if (s == null || s.length() == 0) {
return "";
}
if (k == 0) {
return s;
}
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
PriorityQueue<Character> queue = new PriorityQueue<>(new Comparator<Character>() {
public int compare(Character c1, Character c2) {
if (map.get(c1).intValue() != map.get(c2).intValue()) {
return map.get(c2) - map.get(c1);
}
return c1.compareTo(c2);
}
});
for (char c : map.keySet()) {
queue.offer(c);
}
int len = s.length();
StringBuilder result = new StringBuilder();
while (!queue.isEmpty()) {
int count = Math.min(len, k);
List<Character> list = new ArrayList<>();
for (int i = 0; i < count; i++) {
if (queue.isEmpty()) {
return "";
}
char c = queue.poll();
result.append(c);
len--;
map.put(c, map.get(c) - 1);
if (map.get(c) > 0) {
list.add(c);
}
}
for (char c : list) {
queue.offer(c);
}
}
return result.toString();
}
}
Hope this helps,
Michael