# LeetCode 767: Reorganize String

## Problem Restatement

We are given a string `s`.

We need to rearrange its characters so that no two adjacent characters are the same.

Return any valid rearrangement.

If no valid rearrangement exists, return an empty string.

The problem allows any correct answer, not one specific output. The official statement says to rearrange the characters so adjacent characters are not equal, or return `""` if impossible.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A lowercase English string `s` |
| Output | Any rearranged string with no equal adjacent characters |
| Impossible case | Return `""` |
| Constraint | Use exactly the same characters as `s` |

Example function shape:

```python
def reorganizeString(s: str) -> str:
    ...
```

## Examples

Example 1:

```python
s = "aab"
```

Output:

```python
"aba"
```

The two `a` characters are separated by `b`, so this is valid.

Example 2:

```python
s = "aaab"
```

Output:

```python
""
```

There are too many `a` characters.

No matter how we arrange the string, at least two `a` characters must be adjacent.

## First Thought: Try All Permutations

A direct idea is to generate every permutation of `s` and return the first one where no adjacent characters are equal.

This is not practical.

A string of length `n` can have up to:

```text
n!
```

permutations.

We need a greedy construction.

## Key Insight

The character with the largest remaining frequency is the most dangerous one.

If we delay it too much, we may be forced to place it next to itself later.

So at each step, we want to choose the most frequent character that is different from the previously placed character.

A max heap is a good fit for this.

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

```python
(-count, character)
```

The smallest negative count represents the largest real count.

## Impossible Case

Let `n = len(s)`.

If some character appears more than:

```text
(n + 1) // 2
```

times, then no valid arrangement exists.

Why?

The most frequent character needs enough other characters to separate its copies.

For example:

```python
s = "aaab"
```

Here `a` appears `3` times, and `n = 4`.

The limit is:

```text
(4 + 1) // 2 = 2
```

Since `3 > 2`, it is impossible.

## Greedy Heap Method

We keep one previously used character out of the heap for one round.

This prevents the same character from being chosen twice in a row.

At each step:

1. Pop the most frequent available character.
2. Append it to the answer.
3. Decrease its remaining count.
4. Push the previous character back into the heap if it still has remaining count.
5. Store the current character as the previous character for the next round.

This way, the character just used cannot be selected immediately again.

## Algorithm

1. Count character frequencies.
2. If the largest frequency is greater than `(len(s) + 1) // 2`, return `""`.
3. Build a max heap using negative counts.
4. Keep:
   1. `prev_count = 0`
   2. `prev_char = ""`
5. While the heap is not empty:
   1. Pop the most frequent available character.
   2. Append it to the answer.
   3. Decrease its remaining count.
   4. If the previous character still has remaining count, push it back.
   5. Save the current character as previous.
6. Return the joined answer.

## Correctness

If a character appears more than `(n + 1) // 2` times, there are not enough other characters to separate all copies of it. Therefore, returning `""` in that case is correct.

Otherwise, the greedy heap algorithm always chooses the character with the largest remaining frequency among the characters allowed at the current position.

The most recently used character is temporarily withheld from the heap, so the next character chosen cannot be equal to it. Therefore, the algorithm never creates two equal adjacent characters.

After one different character has been placed, the previous character can safely return to the heap, because placing it later will not make it adjacent to its earlier copy.

The algorithm decreases exactly one character count at each step and appends exactly one character. Since every appended character comes from the original frequency counts, and every count is eventually consumed, the returned string contains exactly the same multiset of characters as `s`.

Thus, when the feasibility condition holds, the algorithm returns a valid reorganization.

## Complexity

Let `n = len(s)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log 26)` | Each character placement uses heap operations over lowercase letters |
| Space | `O(26)` | The heap and counter store lowercase letters |

Since there are only 26 lowercase English letters, the time complexity is effectively `O(n)`.

## Implementation

```python
from collections import Counter
import heapq

class Solution:
    def reorganizeString(self, s: str) -> str:
        count = Counter(s)

        if max(count.values()) > (len(s) + 1) // 2:
            return ""

        heap = []

        for ch, freq in count.items():
            heapq.heappush(heap, (-freq, ch))

        answer = []
        prev_count = 0
        prev_char = ""

        while heap:
            freq, ch = heapq.heappop(heap)
            answer.append(ch)

            freq += 1

            if prev_count < 0:
                heapq.heappush(heap, (prev_count, prev_char))

            prev_count = freq
            prev_char = ch

        return "".join(answer)
```

## Code Explanation

We first count characters:

```python
count = Counter(s)
```

Then we check whether a valid answer is possible:

```python
if max(count.values()) > (len(s) + 1) // 2:
    return ""
```

The heap stores negative frequencies:

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

So the most frequent character is popped first.

The variables:

```python
prev_count = 0
prev_char = ""
```

store the character used in the previous step, if it still has remaining count.

Inside the loop, we pop the most frequent available character:

```python
freq, ch = heapq.heappop(heap)
```

Then append it:

```python
answer.append(ch)
```

Because `freq` is negative, using one copy means adding `1`:

```python
freq += 1
```

If the previous character still has copies left, push it back now:

```python
if prev_count < 0:
    heapq.heappush(heap, (prev_count, prev_char))
```

Then store the current character as the previous one:

```python
prev_count = freq
prev_char = ch
```

This delay prevents the same character from being chosen twice in a row.

## Testing

Because many outputs may be valid, tests should check validity rather than exact equality.

```python
from collections import Counter

def is_valid(original: str, result: str) -> bool:
    if result == "":
        max_freq = max(Counter(original).values())
        return max_freq > (len(original) + 1) // 2

    if Counter(original) != Counter(result):
        return False

    for i in range(1, len(result)):
        if result[i] == result[i - 1]:
            return False

    return True

def run_tests():
    s = Solution()

    result = s.reorganizeString("aab")
    assert is_valid("aab", result)

    result = s.reorganizeString("aaab")
    assert result == ""

    result = s.reorganizeString("vvvlo")
    assert is_valid("vvvlo", result)

    result = s.reorganizeString("a")
    assert is_valid("a", result)

    result = s.reorganizeString("aa")
    assert result == ""

    result = s.reorganizeString("abc")
    assert is_valid("abc", result)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"aab"` | Basic possible case |
| `"aaab"` | Impossible because one character is too frequent |
| `"vvvlo"` | Repeated dominant character but still possible |
| `"a"` | Single character is already valid |
| `"aa"` | Two identical characters cannot be separated |
| `"abc"` | All distinct characters |