**Solution**

**Rearrange String k Distance Apart** https://leetcode.com/problems/rearrange-string-k-distance-apart/

**Algorithm**

- Note there are two versions. One version of the problem is "Rearrange String Exactly k Distance Apart". Solution 1 has the solution for it. It is also mentioned in geekforgeeks.
- Our problem is: "Rearrange String atleast k Distance Apart"
- For every position in the result, fill it with the character with the highest frequency as long as it can be filled validly. Validity means to ensure that the previous occurence of this charcter was k apart.

```
from collections import Counter
class Solution(object):
def rearrangeString(self, s, k):
"""
:type str: str
:type k: int
:rtype: str
"""
f_map = Counter(s)
result = [None]*len(s)
last = {}
for i in range(len(s)):
max_ch, max_f = None, 0
# Iterate all elements in frequency map and pick the valid one with highest frequency.
for k1,v1 in f_map.items():
if (v1 > max_f) and (k1 not in last or last[k1]+k<=i):
max_ch, max_f = k1,v1
if max_ch == None:
return ""
# Add the character to result. Reduce the frequency. Update the position for last occurence.
result[i] = max_ch
f_map[max_ch] = f_map[max_ch] - 1
last[max_ch] = i
return "".join(result)
```