LeetCode 649: Dota2 Senate

Problem Restatement

We are given a string senate.

Each character represents one senator:

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:

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

Example function shape:

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

Examples

Example 1:

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:

"Radiant"

Example 2:

senate = "RDD"

Turn order:

Output:

"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:

The smaller front index acts first.

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

If:

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:

r + n

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

If:

d < r

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

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

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:

radiant = deque()
dire = deque()

Then we store the original positions:

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:

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

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

If r < d, Radiant acts first:

radiant.append(r + n)

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

If d < r, Dire acts first:

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).

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.

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

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: