418. Senate Showdown
A council is made of senators from two factions, R (Radiant) and D (Dire), listed in senate in speaking order. Voting is held in rounds. In a round the senators who are still active speak in order, and when a senator speaks they either ban one senator of the rival faction (that senator loses all rights from then on and is skipped) or, if every remaining senator belongs to their own faction, announce victory for their faction.
Every senator plays optimally for their own faction, which means each one always bans the next active rival who would otherwise speak soonest, and the rounds repeat in the same order until one faction wins. Return "Radiant" or "Dire" for the winning faction.
Example 1
- Input:
- senate = "DRRDRDDR"
- Output:
- "Dire"
- Explanation:
In the first round the senator at 0 (D) bans the R at 1, the R at 2 bans the D at 3, the R at 4 bans the D at 5, and the D at 6 bans the R at 7. In the second round the D at 0 bans the R at 2, the R at 4 bans the D at 6, and finally the D at 0 bans the last R. Dire wins.
Example 2
- Input:
- senate = "RRDDD"
- Output:
- "Radiant"
- Explanation:
The two R senators ban D at 2 and D at 3. In round two the D at 4 bans the R at 0, but the R at 1 still speaks before the last D and bans it. Radiant wins.
Constraints
1 ≤ senate.length ≤ 100000senate[i] is 'R' or 'D'.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)