### Problem Statement

Given a string and a number ‘K’, find if the string can be rearranged such that the same characters are at least ‘K’ distance apart from each other.

### Example:

```Input 1: s = "mmpp", K = 2
Output 1: "pmpm"

Input 2: s = "aaaaabbbcccddd", K = 3

### Code

```import java.util.*;

class Innoskrit {

public static String reorganizeString(String str, int k) {

if (k <= 1) {
return str;
}

Map<Character, Integer> freqMap = new HashMap<>();

for (char chr : str.toCharArray()) {
freqMap.put(chr, freqMap.getOrDefault(chr, 0) + 1);
}

PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<Map.Entry<Character, Integer>>(
(e1, e2) -> e2.getValue() - e1.getValue());

Queue<Map.Entry<Character, Integer>> queue = new LinkedList<>();
StringBuilder resultString = new StringBuilder(str.length());

while (!maxHeap.isEmpty()) {
Map.Entry<Character, Integer> currentEntry = maxHeap.poll();

resultString.append(currentEntry.getKey());
currentEntry.setValue(currentEntry.getValue() - 1);
queue.offer(currentEntry);

if (queue.size() == k) {
Map.Entry<Character, Integer> entry = queue.poll();
if (entry.getValue() > 0) {
}
}
}

return resultString.length() == str.length() ? resultString.toString() : "";
}

public static void main(String[] args) {
System.out.println(Innoskrit.reorganizeString("mmpp", 2));
System.out.println(Innoskrit.reorganizeString("aaaaabbbcccddd", 3));
}
}```
```#include <bits/stdc++.h>
using namespace std;

class Innoskrit {
public:
struct comparator {
bool operator()(const pair<int, int> &x, const pair<int, int> &y) {
return y.second > x.second;
}
};

static string reorganizeString(const string &str, int k) {
if (k <= 1) {
return str;
}

unordered_map<char, int> freqMap;
for (char chr : str) {
freqMap[chr]++;
}

priority_queue<pair<char, int>, vector<pair<char, int>>, comparator> maxHeap;

for (auto entry : freqMap) {
maxHeap.push(entry);
}

queue<pair<char, int>> queue;
string resultString;
while (!maxHeap.empty()) {
auto currentEntry = maxHeap.top();
maxHeap.pop();
resultString += currentEntry.first;
currentEntry.second--;
queue.push(currentEntry);
if (queue.size() == k) {
auto entry = queue.front();
queue.pop();
if (entry.second > 0) {
maxHeap.push(entry);
}
}
}

return resultString.length() == str.length() ? resultString : "";
}
};

int main(int argc, char *argv[]) {
cout << Innoskrit::reorganizeString("mmpp", 2) << endl;
cout << Innoskrit::reorganizeString("aaaaabbbcccddd", 3) << endl;
}```
```from heapq import *
from collections import deque

class Pair:

def __init__(self, char, freq):
self.char = char
self.freq = freq

def __lt__(self, other):
return self.freq > other.freq

class Innoskrit:

@staticmethod
def reorganize_string(str, k):
if k <= 1:
return str

freq_map = {}
for char in str:
freq_map[char] = freq_map.get(char, 0) + 1

maxHeap = []

for char, frequency in freq_map.items():
heappush(maxHeap, Pair(char, frequency))

queue = deque()
resultString = []
while maxHeap:
entry = heappop(maxHeap)

resultString.append(entry.char)
entry.freq -= 1
queue.append(entry)
if len(queue) == k:
entry = queue.popleft()
if entry.freq > 0:
heappush(maxHeap, entry)

return ''.join(resultString) if len(resultString) == len(str) else ""

if __name__ == '__main__':

print(Innoskrit.reorganize_string("mmpp", 2))
print(Innoskrit.reorganize_string("aaaaabbbcccddd", 3))```

```pmpm