Dota2 Senate
Medium · Stack & Strings · String · Greedy · Queue
Problem
A senate has senators from two parties, Radiant and Dire, given as a string senate where 'R' and 'D' mark each senator's party, in seating order.
Voting runs in rounds. Within a round, senators act in seating order, and each senator who still has rights does one of two things:
- Ban one other senator, who loses all rights in this round and every later one.
- Announce victory, if every senator who still has rights belongs to their own party.
Banned senators are skipped. Every senator plays as well as possible for their party. Return "Radiant" or "Dire": the party that wins.
Examples
Input: senate = "RDD" Output: "Dire"
R bans the first D, but the second D then bans R.
Input: senate = "DRR" Output: "Radiant"
D bans one R; the other R bans D, and only Radiant is left.
Input: senate = "RRDDD" Output: "Radiant"
Both Rs act first and ban two Ds; the last D bans one R, and the surviving R bans it in the next round.
Constraints
- n == len(senate)
- 1 <= n <= 10^4
- senate[i] is 'R' or 'D'
Approaches
- Baseline: walk the seats round after round — time O(n²), space O(n)
Follow-up
Each comparison bans one senator, so the queues finish in O(n) steps. A related question is how many senators are left at the end, or in which order they were banned; the same queues answer both. With three or more parties, "ban the next opponent" is no longer clearly optimal, because helping one rival can hurt you more than another.
Related problems
Start free on Cariara · Coding problems · System design studio
