# Problem Statement
In the world of Dota2, there are two parties: the Radiant and the Dire.
The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise **one** of the two rights:
- **Ban one senator's right:** A senator can make another senator lose all his rights in this and all the following rounds.
- **Announce the victory:** If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.
Given a string `senate` representing each senator's party belonging. The character `'R'` and `'D'` represent the Radiant party and the Dire party. Then if there are `n` senators, the size of the given string will be `n`.
The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.
Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be `"Radiant"` or `"Dire"`.
## Constraints
- `n == senate.length`
- `1 <= n <=` $10^4$
- `senate[i]` is either `'R'` or `'D'`.
# Solution
First, we count the number of `"R"`s and`"D"`s. As we go through our main loop, these numbers will go down, and when one hits 0, whichever is left is our answer.
```python
r = senate.count("R")
d = senate.count("D")
```
Because we'll be editing the valid senators and looping through multiple times, we initialize a [[Queue]] and fill it with the initial senators.
```python
q = deque(list(senate))
```
This problem can be solved with a [[Greedy]] strategy. For each senator we encounter, they will want to nullify the **next** opposing senator. And if we run into groups of one senator type, they can nullify the same amount of the opposite party.
Each time we dequeue a senator, we need to know if they have been nullified or not. We can keep track of this in a variable called `swing`. If `swing` is positive, `"D"` is getting nullified. If `swing` is negative, `"R"` is getting nullified.
```python
swing = 0
```
Right now, `swing` is 0, meaning there are no new senators to be nullified. However, when we dequeue our first senator, the value changes depending on the party.
Lets use the input `"RRDDD"` as an example. Our queue looks like this: `(HEAD)[R, R, D, D, D](TAIL)`.
- Our first senator to be dequeued is `"R"`. He has not been nullified and will want to nullify the **next non-nullified opposing senator**. We keep track of this by enqueueing him for next round and increasing `swing` by `1`. Now the queue looks like so: `(HEAD)[R, D, D, D, R](TAIL)`
- The next senator we dequeue is also `"R"`. Since `swing` is non-negative, he is also is not nullified and will use his vote to nullify the **next non-nullified opposing senator**. Thus, we enqueue him for next round and increase `swing`to `2`. Now the queue looks like so: `(HEAD)[D, D, D, R, R](TAIL)`
- Now we dequeue our first `"D"`. However. We know he has been nullified because `swing` is positive. Therefore, he has no vote and we do not enqueue him for next round. We also decrease `swing` back to `1`, since now there is only one more `"D"` to be nullified. Lastly, we decrease `d` by `1` to correctly keep track of the number of senators who can vote. Now the queue looks like so: `(HEAD)[D, D, R, R](TAIL)`
- We dequeue and nullify another `"D"` because `swing` is still positive. We decrease `swing` down to `0` and decrease `d` by `1`.`(HEAD)[D, R, R](TAIL)`
- We dequeue our third `"D"`, but he is not nullified because `swing` is `0`. Thus, we enqueue him for next round and decrease `swing` to `-1`. `[R, R, D]`
- We dequeue an `"R"`. Since `swing` is negative, he is not re-enqueued, we update `swing` back to `0`, and decrease `r` by 1. `(HEAD)[R, D](TAIL)`
- The last two queue states are hopefully easily extrapolated:`[D, R]`, `[R]`.
- Now that all `"D"`s have been nullified, we return `"Radiant"`
```python
while True:
if d == 0: return "Radiant"
if r == 0: return "Dire"
curr = q.popleft()
if curr == "R":
if swing < 0:
r -= 1
swing += 1
continue
else:
swing += 1
q.append(curr)
elif curr == "D":
if swing > 0:
d -= 1
swing -= 1
continue
else:
swing -= 1
q.append(curr)
```
Time Complexity: O$(n)$ | Space Complexity: O$(n)$