Dota2 Senate

The key idea

Each senator should ban the very next opponent in voting order, because that opponent is the soonest threat to act against their own party. A senator who survives a round comes back later, so model each party as a queue of indices and let the lower index act first each turn.

Problem

In the world of Dota2, there are two parties: the Radiant and the Dire. The Dota2 senate consists of senators from both parties, given as a string senate where 'R' marks a Radiant senator and 'D' marks a Dire senator. The senate votes in rounds. In each round, every still-eligible senator, taken in the original order, may exercise one of two rights: ban one other senator's right from this and all future rounds, or, if every remaining senator belongs to their own party, announce victory and decide the outcome. The voting wraps around round after round until one side declares victory. Assuming every senator plays optimally for their own party, predict which party finally announces victory and return either "Radiant" or "Dire".

Constraints

1 <= senate.length <= 10^4
senate[i] is either 'R' or 'D'

Examples

Input: senate = "RD" Output: "Radiant"

Input: senate = "RDD" Output: "Dire"

Complexity

Time: O(n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →