keetcoder

# 649. Dota2 Senate

LeetCode Problem Link (opens new window)

In the world of Dota2, there are two factions: Radiant and Dire.

The Dota2 senate consists of senators from both factions. Now, the senate wants to make a decision regarding a change in a Dota2 game. They vote by a round-based voting process. In each round, each senator can exercise one of the following rights:

  1. Ban the rights of another senator: A senator can make another senator lose all their rights in this round and future rounds.

  2. Announce victory: If a senator finds that all remaining senators eligible to vote belong to the same faction, they can announce victory and decide on the change in the game.

Given a string representing the faction of each senator. The letters "R" and "D" represent Radiant and Dire respectively. If there are n senators, the given string will have a size of n.

The round-based process starts from the first senator in the given order and ends with the last senator. This process continues until the voting ends. All senators who lose rights are skipped during the process.

Assuming each senator is smart enough to make the best strategy for their party, you need to predict which side will eventually announce victory and decide the changes in the Dota2 game. The output should be "Radiant" or "Dire".

Example 1:

  • Input: "RD"
  • Output: "Radiant"
  • Explanation: The first senator belongs to the Radiant faction, and they can use their right to ban the second senator, so the second senator will be skipped as they have no rights. Then, in the second round, the first senator can declare victory as they are the only one with voting rights.

Example 2:

  • Input: "RDD"
  • Output: "Dire"
  • Explanation: In the first round, the first senator from the Radiant faction can use their right to ban the rights of the second senator. The second senator from the Dire faction will be skipped as their rights are banned. The third senator from the Dire faction can use their right to ban the rights of the first senator. In the second round, only the third senator has the right to vote, so they can declare victory.

# Idea

The problem statement can be quite convoluted, so let's break it down with an example for better understanding.

For instance, with an input of "RRDDD", the process should be as follows:

  • First round: The R from senate[0] bans the D from senate[2], the R from senate[1] bans the D from senate[3], and finally, the D from senate[4] bans the R from senate[0]. This leaves us with "RD", ending the first round!
  • Second round: The R from senate[0] bans the D from senate[1], ending the second round.
  • Third round: Only R remains, so R wins.

The key point to focus on is that when R and D counts are the same, who wins? The answer lies in a persistent elimination process. That is, continue the process of elimination by rounds until only R or D remains.

What should be the strategy for elimination in each round?

For example, consider RDDRD:

In the first round, the R from senate[0] can eliminate the D from senate[1]. Now, should the D from senate[2] eliminate the R from senate[0] or senate[3]?

It is strategic to eliminate the R from senate[3] because when it's this R's turn, it can eliminate the D from senate[4].

Thus, the elimination strategy should be to eliminate your subsequent opponent whenever possible since the previous competitors have already exercised their rights, and subsequent opponents can still exercise their rights to eliminate your comrades!

Therefore, the local optimal strategy is to eliminate the subsequent opponents whenever you have the opportunity. The global optimal strategy is to win the maximum benefit for your faction.

The local optimal can lead to the global optimal. Let's test this with a greedy algorithm approach.

If you are not familiar with the basics of greedy algorithms, you can take a look at this Greedy Algorithm Fundamentals (opens new window). It will give you a basic understanding of greedy strategies.

# Code Implementation

Implementing the code to simulate eliminating the subsequent opponents in each round is quite troublesome.

Here’s a technique: use a variable to record how many enemy opponents have appeared before the current senator to determine whether they have been eliminated. We use flag for this purpose.

CPP code:

class Solution {
public:
    string predictPartyVictory(string senate) {
        // R = true indicates that after the cycle ends, there are still Rs in the string. The same for D.
        bool R = true, D = true;
        // When flag > 0, R appears before D and can ban D. When flag < 0, D appears before R and can ban R.
        int flag = 0;
        while (R && D) { // Once R or D is false, end the loop, which means only R or D is left after this round.
            R = false;
            D = false;
            for (int i = 0; i < senate.size(); i++) {
                if (senate[i] == 'R') {
                    if (flag < 0) senate[i] = 0; // Ban R, with R currently as false
                    else R = true; // If not banned, there is R at the end of this cycle
                    flag++;
                }
                if (senate[i] == 'D') {
                    if (flag > 0) senate[i] = 0;
                    else D = true;
                    flag--;
                }
            }
        }
        // After the loop ends, either R or D must be true
        return R == true ? "Radiant" : "Dire";
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# Code in Other Languages

# Java

class Solution {
    public String predictPartyVictory(String senateStr) {
        Boolean R = true, D = true;
        int flag = 0;
        byte[] senate =  senateStr.getBytes();
        while (R && D) {
            R = false;
            D = false;
            for (int i = 0; i < senate.length; i++) {
                if (senate[i] == 'R') {
                    if (flag < 0) senate[i] = 0;
                    else R = true;
                    flag++;
                }
                if (senate[i] == 'D') {
                    if (flag > 0) senate[i] = 0;
                    else D = true;
                    flag--;
                }
            }
        }
        return R == true ? "Radiant" : "Dire";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# Python

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        R, D = True, True
        flag = 0
        senate = list(senate)
        while R and D:
            R = False
            D = False
            for i in range(len(senate)) :
                if senate[i] == 'R' :
                    if flag < 0: senate[i] = '0'
                    else: R = True
                    flag += 1
                if senate[i] == 'D':
                    if flag > 0: senate[i] = '0'
                    else: D = True
                    flag -= 1
        return "Radiant" if R else "Dire"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# Go

func predictPartyVictory(senateStr string) string {
	R, D := true, true
	flag := 0

	senate := []byte(senateStr)
	for R && D {
		R = false
		D = false
		for i := 0; i < len(senate); i++ {
			if senate[i] == 'R' {
				if flag < 0  {
					 senate[i] = 0  
				} else {
					R = true 
				}
				flag++;
			}
			if (senate[i] == 'D') {
				if flag > 0 {
					senate[i] = 0
				} else  {
					D = true
				}
				flag--
			}
		}
	}
	if R {
		return "Radiant"
	}
	return "Dire"
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# JavaScript

var predictPartyVictory = function(senateStr) {
    let R = true, D = true;
    let flag = 0;
    let senate = senateStr.split('');
    while(R && D){
        R = false;
        D = false;
        for(let i = 0; i < senate.length; i++){
            if(senate[i] === 'R'){
                if(flag < 0) senate[i] = 0;
                else R = true;
                flag++;
            }
            if(senate[i] === 'D'){
                if(flag > 0) senate[i] = 0;
                else D = true;
                flag--;
            }
        }
    }
    return R ? "Radiant" : "Dire";
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# TypeScript

function predictPartyVictory(senate: string): string {
    let deltaRDCnt: number = 0;
    let hasR: boolean = true,
        hasD: boolean = true;
    const senateArr: string[] = senate.split('');
    while (hasR && hasD) {
        hasR = false;
        hasD = false;
        for (let i = 0, length = senateArr.length; i < length; i++) {
            if (senateArr[i] === 'R') {
                if (deltaRDCnt < 0) {
                    senateArr[i] = '';
                } else {
                    hasR = true;
                }
                deltaRDCnt++;
            } else if (senateArr[i] === 'D') {
                if (deltaRDCnt > 0) {
                    senateArr[i] = '';
                } else {
                    hasD = true;
                }
                deltaRDCnt--;
            }
        }
    }
    return hasR ? 'Radiant' : 'Dire';
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Last updated:: 9/4/2025, 3:19:38 PM
Copyright © 2025 keetcoder