# LeetCode 649: Dota2 Senate

## Problem Restatement

We are given a string `senate`.

Each character represents one senator:

| Character | Party |
|---|---|
| `"R"` | Radiant |
| `"D"` | Dire |

The voting process happens in rounds from left to right.

On a senator's turn, if they still have voting rights, they can ban one senator from the opposite party. A banned senator loses voting rights for the current and all future rounds.

If all remaining senators with voting rights belong to the same party, that party wins.

Return:

| Winner | Return |
|---|---|
| Radiant | `"Radiant"` |
| Dire | `"Dire"` |

The process order follows the original string order, and senators act optimally for their party. The official statement uses examples such as `senate = "RD"` returning `"Radiant"`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `senate` containing only `"R"` and `"D"` |
| Output | `"Radiant"` or `"Dire"` |
| Turn order | From left to right, repeated by rounds |
| Ban effect | Removes an opponent's rights permanently |

Example function shape:

```python
def predictPartyVictory(senate: str) -> str:
    ...
```

## Examples

Example 1:

```python
senate = "RD"
```

The first senator is Radiant.

Radiant acts first and bans the Dire senator.

In the next round, only Radiant has voting rights.

Output:

```python
"Radiant"
```

Example 2:

```python
senate = "RDD"
```

Turn order:

| Step | Action |
|---|---|
| `R` at index `0` | bans the first `D` |
| `D` at index `1` | already banned, skipped |
| `D` at index `2` | bans `R` |
| next round | only Dire remains |

Output:

```python
"Dire"
```

## First Thought: Simulate the String Directly

We could repeatedly scan the string.

When an active senator appears, they ban the next active opponent.

This works, but it is awkward because we need to track which senators are banned, skip them in later rounds, and wrap around to the start.

A cleaner method is to store the active turn order explicitly.

## Key Insight

Use two queues:

| Queue | Stores |
|---|---|
| `radiant` | indices of active Radiant senators |
| `dire` | indices of active Dire senators |

The smaller front index acts first.

Suppose the next Radiant senator has index `r`, and the next Dire senator has index `d`.

If:

```python
r < d
```

then Radiant acts before Dire. Radiant bans that Dire senator.

The Radiant senator survives to the next round, so we put them back with index:

```python
r + n
```

Adding `n` means the senator comes after all remaining senators in the current round.

If:

```python
d < r
```

then Dire acts first, bans that Radiant senator, and goes back into the queue as:

```python
d + n
```

This simulates round order without manually rebuilding the string.

## Algorithm

1. Let `n = len(senate)`.
2. Put every Radiant index into `radiant`.
3. Put every Dire index into `dire`.
4. While both queues are non-empty:
   1. Pop the next Radiant index.
   2. Pop the next Dire index.
   3. The smaller index acts first and bans the other.
   4. Reinsert the winner's index plus `n`.
5. If `radiant` is non-empty, return `"Radiant"`.
6. Otherwise, return `"Dire"`.

## Implementation

```python
from collections import deque

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate)

        radiant = deque()
        dire = deque()

        for i, party in enumerate(senate):
            if party == "R":
                radiant.append(i)
            else:
                dire.append(i)

        while radiant and dire:
            r = radiant.popleft()
            d = dire.popleft()

            if r < d:
                radiant.append(r + n)
            else:
                dire.append(d + n)

        return "Radiant" if radiant else "Dire"
```

## Code Explanation

We create two queues:

```python
radiant = deque()
dire = deque()
```

Then we store the original positions:

```python
for i, party in enumerate(senate):
    if party == "R":
        radiant.append(i)
    else:
        dire.append(i)
```

The front of each queue is the next active senator from that party.

During each step:

```python
r = radiant.popleft()
d = dire.popleft()
```

we compare the next Radiant senator and the next Dire senator.

If `r < d`, Radiant acts first:

```python
radiant.append(r + n)
```

The Dire senator is not reinserted, because they were banned.

If `d < r`, Dire acts first:

```python
dire.append(d + n)
```

The Radiant senator is not reinserted.

The loop stops when one party has no active senators left.

## Correctness

The queues store active senators in the order in which they will act. Initially, this is exactly the order of indices in the input string.

At each step, the front Radiant senator and the front Dire senator are the earliest remaining senators from their parties. The smaller index among them acts first according to the voting order.

The senator who acts first can optimally ban the earliest available opponent, because preventing the next opposing action is always at least as good as banning a later opponent. The queue comparison does exactly this: the winner is reinserted, and the loser is removed.

Adding `n` to the winner's index places that senator in the next round after all current-round senators, preserving cyclic order.

Thus each loop iteration correctly simulates one ban action while maintaining the future turn order.

When one queue becomes empty, no senator from that party still has voting rights. Therefore, all remaining active senators belong to the other party, which can announce victory.

So the returned party is correct.

## Complexity

Let `n = len(senate)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each ban removes one senator, and each queue operation is `O(1)` |
| Space | `O(n)` | The queues store active senator indices |

## Alternative Solution: Ban Counters

Another simulation uses one queue of senator characters and two ban counters.

When an `R` appears, it is banned if there is a pending Dire ban. Otherwise, it bans a future Dire senator and is pushed back.

```python
from collections import deque

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        queue = deque(senate)

        radiant_count = senate.count("R")
        dire_count = senate.count("D")

        ban_radiant = 0
        ban_dire = 0

        while radiant_count > 0 and dire_count > 0:
            senator = queue.popleft()

            if senator == "R":
                if ban_radiant > 0:
                    ban_radiant -= 1
                    radiant_count -= 1
                else:
                    ban_dire += 1
                    queue.append("R")
            else:
                if ban_dire > 0:
                    ban_dire -= 1
                    dire_count -= 1
                else:
                    ban_radiant += 1
                    queue.append("D")

        return "Radiant" if radiant_count > 0 else "Dire"
```

The two-queue version is usually easier to reason about because the next acting senator is represented directly by index order.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.predictPartyVictory("RD") == "Radiant"
    assert s.predictPartyVictory("RDD") == "Dire"
    assert s.predictPartyVictory("R") == "Radiant"
    assert s.predictPartyVictory("D") == "Dire"
    assert s.predictPartyVictory("RRDDD") == "Radiant"
    assert s.predictPartyVictory("DRRDRDRDRDDRDRDR") == "Dire"

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"RD"` | First Radiant bans Dire |
| `"RDD"` | Dire eventually wins |
| Single `"R"` | Immediate Radiant victory |
| Single `"D"` | Immediate Dire victory |
| `"RRDDD"` | Turn order beats raw count |
| Mixed longer string | Checks repeated round ordering |