Medium

Quiz

#649 Dota2 Senate

APPROACH

In the Dota2 senate, 'R' (Radiant) and 'D' (Dire) senators take turns in the order given by string senate. Each senator may either ban one future opponent (removing them permanently) or, if all remaining senators belong to their own party, declare victory. Assuming every senator plays optimally, determine which party wins and return "Radiant" or "Dire".

Example 1:

Input: senate = "RD"

Output: "Radiant"

Explanation:

The first senator comes from Radiant and he can just ban the next senator's right in round 1.

And the second senator can't exercise any rights anymore since his right has been banned.

And in round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2:

Input: senate = "RDD"

Output: "Dire"

Explanation:

The first senator comes from Radiant and he can just ban the next senator's right in round 1.

And the second senator can't exercise any rights anymore since his right has been banned.

And the third senator comes from Dire and he can ban the first senator's right in round 1.

And in round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

1 of 4

1:00

What is the optimal approach for this problem?