# LeetCode 358: Rearrange String k Distance Apart

## Problem Restatement

We are given a non-empty lowercase string `s` and an integer `k`.

We need to rearrange the characters of `s` so that the same characters are at least distance `k` from each other.

If this is possible, return any valid rearranged string.

If this is impossible, return an empty string `""`.

For example, if character `a` appears at index `i`, then the next `a` can only appear at index `i + k` or later. The official examples include `s = "aabbcc", k = 3`, where `"abcabc"` is valid, and `s = "aaabc", k = 3`, where no valid rearrangement exists.

## Input and Output

| Item | Meaning |
|---|---|
| Input | String `s` and integer `k` |
| Output | A rearranged string or `""` |
| Rule | Equal characters must be at least `k` indices apart |
| Characters | Lowercase English letters |
| Valid answers | Any valid rearrangement is accepted |

Example function shape:

```python
def rearrangeString(s: str, k: int) -> str:
    ...
```

## Examples

Example 1:

```python
s = "aabbcc"
k = 3
```

One valid answer is:

```python
"abcabc"
```

The two `a` characters are at indices `0` and `3`.

Their distance is:

```python
3 - 0 = 3
```

The same is true for `b` and `c`.

So this is valid.

Example 2:

```python
s = "aaabc"
k = 3
```

There are three `a` characters.

They would need to be placed at least `3` positions apart.

A possible spacing would need positions like:

```text
a _ _ a _ _ a
```

That already needs `7` positions, but the string length is only `5`.

So the answer is:

```python
""
```

Example 3:

```python
s = "aaadbbcc"
k = 2
```

One valid answer is:

```python
"abacabcd"
```

The same letters are at least distance `2` apart.

## First Thought: Try All Permutations

A brute force solution would generate every permutation of `s`.

For each permutation, check whether every repeated character is at least `k` distance apart.

This is correct, but far too slow.

If the string length is `n`, the number of permutations can be close to:

```python
n!
```

We need to build the answer greedily.

## Key Insight

This problem is like task scheduling with cooldown.

After we place a character, we should not use it again until `k` positions have passed.

So we need two structures:

| Structure | Purpose |
|---|---|
| Max heap | Pick the character with the highest remaining count |
| Queue | Hold recently used characters until their cooldown ends |

Why choose the most frequent available character?

Because frequent characters are the hardest to place. If we delay them too long, we may get stuck with repeated copies near the end.

At each position:

1. Pick the available character with the highest remaining count.
2. Append it to the answer.
3. Put it into cooldown if it still has remaining copies.
4. Release characters from cooldown after `k` steps.

## Algorithm

If `k <= 1`, return `s`.

There is no effective distance restriction, because equal characters at adjacent indices have distance `1`.

Otherwise:

1. Count character frequencies.
2. Push each character into a max heap as `(-count, char)`.
3. Create a queue for cooldown entries.
4. For each output position:
   - If the heap is empty but the answer is incomplete, return `""`.
   - Pop the most frequent available character.
   - Append it to the result.
   - Decrease its remaining count.
   - Put it into cooldown with the time when it can be used again.
   - If the front cooldown item is ready, push it back into the heap.
5. Return the built string.

A cooldown entry stores:

```python
(ready_index, count, char)
```

where `count` is still negative because we use Python's min-heap as a max-heap.

## Correctness

The heap contains exactly the characters that are currently allowed to be placed. The cooldown queue contains characters that were used recently and cannot yet be reused.

When the algorithm appends a character at position `i`, it places that character into cooldown until position `i + k`. Therefore, the same character cannot be selected again before at least `k` positions have passed.

When a cooldown entry reaches its ready position, the algorithm returns it to the heap. From that point onward, using it again satisfies the required distance.

The greedy choice uses the available character with the largest remaining count. This keeps the most constrained characters from accumulating too many remaining copies late in the process. If the heap becomes empty while the output is still incomplete, every remaining character is still cooling down, so no valid next character can be placed. Returning `""` is correct.

If the algorithm completes the output, every character was used exactly as many times as in `s`, and every repeated character was separated by at least `k` positions. Therefore, the returned string is valid.

## Complexity

Let `n = len(s)` and let `a` be the number of distinct characters.

For lowercase English letters, `a <= 26`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log a)` | Each character placement uses heap operations |
| Space | `O(a)` | Heap, queue, and frequency table store distinct characters |

With lowercase letters, this is effectively `O(n)` time.

## Implementation

```python
from collections import Counter, deque
import heapq

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        if k <= 1:
            return s

        counts = Counter(s)

        heap = []
        for ch, count in counts.items():
            heapq.heappush(heap, (-count, ch))

        wait = deque()
        result = []

        for index in range(len(s)):
            if not heap:
                return ""

            count, ch = heapq.heappop(heap)
            result.append(ch)

            count += 1

            wait.append((index + k, count, ch))

            if wait and wait[0][0] <= index + 1:
                _, ready_count, ready_ch = wait.popleft()

                if ready_count < 0:
                    heapq.heappush(heap, (ready_count, ready_ch))

        return "".join(result)
```

## Code Explanation

We handle the easy case first:

```python
if k <= 1:
    return s
```

When `k` is `0` or `1`, any string order already satisfies the rule.

Then we count characters:

```python
counts = Counter(s)
```

Python has a min-heap, so we store negative counts:

```python
heapq.heappush(heap, (-count, ch))
```

The most frequent character has the smallest negative value, so it comes out first.

The queue stores characters that are temporarily blocked:

```python
wait = deque()
```

At each index, we must place one character.

If no character is available, the arrangement is impossible:

```python
if not heap:
    return ""
```

After choosing a character, we append it:

```python
count, ch = heapq.heappop(heap)
result.append(ch)
```

Then we reduce its remaining count:

```python
count += 1
```

Because `count` is negative, adding `1` moves it closer to zero.

Then we put the character into cooldown:

```python
wait.append((index + k, count, ch))
```

It can be reused only at index `index + k` or later.

After finishing this position, the next output index will be `index + 1`.

So if the cooldown front is ready, we release it:

```python
if wait and wait[0][0] <= index + 1:
    _, ready_count, ready_ch = wait.popleft()

    if ready_count < 0:
        heapq.heappush(heap, (ready_count, ready_ch))
```

We only push it back if it still has remaining copies.

Finally:

```python
return "".join(result)
```

## Testing

```python
def is_valid(s: str, k: int) -> bool:
    last = {}

    for i, ch in enumerate(s):
        if ch in last and i - last[ch] < k:
            return False
        last[ch] = i

    return True

def run_tests():
    sol = Solution()

    ans = sol.rearrangeString("aabbcc", 3)
    assert sorted(ans) == sorted("aabbcc")
    assert is_valid(ans, 3)

    assert sol.rearrangeString("aaabc", 3) == ""

    ans = sol.rearrangeString("aaadbbcc", 2)
    assert sorted(ans) == sorted("aaadbbcc")
    assert is_valid(ans, 2)

    assert sol.rearrangeString("aa", 0) == "aa"
    assert sol.rearrangeString("aa", 1) == "aa"

    ans = sol.rearrangeString("a", 2)
    assert ans == "a"

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"aabbcc", 3` | Valid rearrangement exists |
| `"aaabc", 3` | Impossible case |
| `"aaadbbcc", 2` | Official-style mixed-frequency case |
| `k = 0` | No distance restriction |
| `k = 1` | Adjacent equal characters allowed |
| Single character | Always valid |