Dota2 Senate

Problem

Two parties, Radiant ('R') and Dire ('D'), sit in a senate. You are given a string senate where each character is the party of one senator, listed in the order they will act. Voting happens in round-robin order, cycling through the survivors again and again.

When it is a senator’s turn, they may exercise one right: ban any one senator from the other party, removing that senator from all future rounds. (A rational senator always uses this right — passing never helps.) The process repeats, skipping banned senators, until every remaining senator belongs to one party. Return the winning party: "Radiant" or "Dire".

Because each senator plays optimally for their own party, the question is really: given the seating order, which party can guarantee the win?

Examples

• senate = "RD" → "Radiant" — R acts first and bans D; only R remains.
• senate = "RDD" → "Dire" — R bans one D. The remaining D (who has not acted yet this round) then bans R. Only D’s remain.
• senate = "RRDDD" → "Radiant" — the two R’s act first each lap and pick off D’s faster than the three D’s can retaliate, despite being outnumbered.

Constraints

• 1 <= len(senate) <= 10^4
• senate contains only 'R' and 'D', and both letters appear at least once.

An O(n) or O(n log n) solution is expected; the number of ban rounds can be large, so naive re-scanning is too slow.

Think about it first

TL;DR

Two index queues; each round the earlier senator bans the other party’s front senator and re-queues at index + n — O(n) time, O(n) space.

Approach 1 — Brute force: simulate the seating list literally

Keep a list of surviving senators. Walk it in order; each acting senator scans forward (wrapping around) for the nearest opponent and marks them banned. Repeat laps until only one party remains.

from collections import deque
from typing import List

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        alive = list(senate)
        while 'R' in alive and 'D' in alive:
            n = len(alive)
            banned = [False] * n
            for i in range(n):
                if banned[i]:
                    continue
                # ban the nearest opponent ahead, wrapping around
                for step in range(1, n):
                    j = (i + step) % n
                    if not banned[j] and alive[j] != alive[i]:
                        banned[j] = True
                        break
            alive = [c for i, c in enumerate(alive) if not banned[i]]
        return "Radiant" if 'R' in alive else "Dire"

Complexity: each lap is O(n^2) (every senator may scan the whole list), and a lap removes at most half the senators, so O(log n) laps → O(n^2 log n). At n = 10^4 the inner quadratic scan is the killer.

Approach 2 — Greedy with two queues

The greedy-choice property (why the local pick is globally optimal): when a senator acts, the only choice that can never be improved upon is to ban the nearest upcoming opponent — the opposing senator who would act soonest. Suppose instead you banned some later opponent Y and spared the nearest opponent X. Then X acts on schedule and bans one of your allies before Y would ever have mattered; you have strictly weakened your side and left the most imminent threat alive. Removing the soonest-acting opponent delays the enemy’s next move as far as possible, and no alternative target dominates it. So “ban the nearest future opponent” is a safe greedy move at every step — there is never a reason to save it for later.

Concretely, keep two queues holding the turn indices of each party’s living senators. The senator with the smaller index acts first; they ban the opponent at the front of the other queue (that opponent is the nearest future one, since queues stay sorted by turn order). The winner survives and rejoins the queue for the next lap at index i + n, which keeps all indices comparable across laps.

from collections import deque

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate)
        radiant = deque(i for i, c in enumerate(senate) if c == 'R')
        dire = deque(i for i, c in enumerate(senate) if c == 'D')
        while radiant and dire:
            r, d = radiant.popleft(), dire.popleft()
            if r < d:               # R acts first, bans this D
                radiant.append(r + n)
            else:                   # D acts first, bans this R
                dire.append(d + n)
        return "Radiant" if radiant else "Dire"

Walkthrough on senate = "RRDDD" (indices 0..4, n = 5):

1. radiant = [0,1], dire = [2,3,4].
2. Pop r=0, d=2: 0 < 2, so R acts first and bans D#2. R re-queues 0+5=5 → radiant=[1,5], dire=[3,4].
3. Pop r=1, d=3: 1 < 3, R bans D#3. radiant=[5,6], dire=[4].
4. Pop r=5, d=4: 4 < 5, D acts first and bans R#5. dire=[9], radiant=[6].
5. Pop r=6, d=9: 6 < 9, R bans D#9. radiant=[11], dire=[] → “Radiant”. ✅

Even though Dire outnumbers Radiant 3–2, the two R’s sit earlier in the order, so they always fire first and out-trade the D’s. Raw majority does not decide it — position does.

Sanity check senate = "RD": radiant=[0], dire=[1]. Pop r=0,d=1: 0<1 → R bans D, radiant=[2], dire=[] → “Radiant”. ✅

Complexity: every popleft permanently removes one senator or advances one by a full lap; total operations are O(n) because each of the n senators can be re-queued only until the shorter party runs out, bounded by O(n) amortized. Time O(n), space O(n) for the two queues.

Common pitfalls

• Banning the global first opponent instead of the nearest one after the acting senator — the queues already encode “nearest upcoming,” so trust the front-vs-front comparison rather than re-searching.
• Forgetting to re-queue the survivor at i + n; without the offset, laps stop interleaving and the loop misbehaves.
• Assuming the majority party always wins. Position matters: leading senators of a smaller-but-earlier bloc can eliminate the majority’s front-runners each lap.

Pattern takeaway

Greedy on an ordered process: when every actor moves in a fixed sequence and each move eliminates a competitor, the optimal target is almost always the nearest future competitor — killing the soonest threat dominates saving it. Encode “turn order” as indices in a queue and let the smaller index win each showdown.