The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

Ban one senator’s right: A senator can make another senator lose all his rights in this and all the following rounds.
Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.

Given a string senate representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party. Then if there are n senators, the size of the given string will be n.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be "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.

Constraints:

n == senate.length
1 <= n <= 104
senate[i] is either 'R' or 'D'.

Explanation

The key to solving this problem is to simulate the voting process using queues. Here’s a step-by-step breakdown:

🤖Initialization:

Create two queues, one for Radiant senators and one for Dire senators.
Store the indices of each senator in their respective queues. This is crucial for tracking their positions in the circular senate.

🤖Simulation Loop:

While both queues are not empty (meaning both parties still have senators):
Compare the indices of the senators at the front of each queue.
The senator with the smaller index gets to ban the other senator.
Remove the banned senator from their queue.
The banning senator is then moved to the back of their queue, with their index updated to reflect the circular nature of the senate. (Add the total senate length to their original index).

🤖Determine the Winner:

Once one of the queues becomes empty, the party represented by the non-empty queue is the winner.

Pseudocode

function predictPartyVictory(senate):
    radiantQueue = empty queue
    direQueue = empty queue
    senateLength = length of senate

    // Initialize queues
    for i = 0 to senateLength - 1:
        if senate[i] == 'R':
            enqueue i into radiantQueue
        else:
            enqueue i into direQueue

    // Simulate voting
    while radiantQueue is not empty AND direQueue is not empty:
        radiantIndex = front of radiantQueue
        direIndex = front of direQueue

        if radiantIndex < direIndex:
            dequeue from direQueue
            enqueue (radiantIndex + senateLength) into radiantQueue
            dequeue from radiantQueue
        else:
            dequeue from radiantQueue
            enqueue (direIndex + senateLength) into direQueue
            dequeue from direQueue

    // Determine winner
    if radiantQueue is not empty:
        return "Radiant"
    else:
        return "Dire"

Implementation

🐍Python

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        """
        Predicts the winner of a senate vote based on the given rules.

        Args:
            senate: A string representing the senate, where 'R' denotes Radiant and 'D' denotes Dire.

        Returns:
            "Radiant" if Radiant wins, "Dire" if Dire wins.
        """
        radiant = []  # Queue to store the indices of Radiant senators
        dire = []     # Queue to store the indices of Dire senators
        n = len(senate) # Length of the senate string

        # Initialize the queues with the indices of each senator
        for i, s in enumerate(senate):
            if s == 'R':
                radiant.append(i)
            else:
                dire.append(i)

        # Simulate the voting process until one party has no senators left
        while radiant and dire:
            # Check which senator is next in line
            if radiant[0] < dire[0]:
                # Radiant senator bans the next Dire senator
                dire.pop(0)  # Remove the next Dire senator from the queue
                # Radiant senator is added back to the queue, but with an updated index to simulate the circular nature
                radiant.append(radiant[0] + n)
                radiant.pop(0) #remove the current radiant senator
            else:
                # Dire senator bans the next Radiant senator
                radiant.pop(0) #Remove the next radiant senator from the queue.
                # Dire senator is added back to the queue, but with an updated index to simulate the circular nature
                dire.append(dire[0] + n)
                dire.pop(0) #remove the current dire senator.

        # Determine the winner based on which queue is not empty
        return "Radiant" if radiant else "Dire"

🟡Typescript

function predictPartyVictory(senate: string): string {
    // Queues to store the indices of Radiant and Dire senators
    const radiant: number[] = [];
    const dire: number[] = [];
    const n: number = senate.length; // Length of the senate string

    // Populate the queues with senator indices
    for (let i = 0; i < n; i++) {
        if (senate[i] === 'R') {
            radiant.push(i);
        } else {
            dire.push(i);
        }
    }

    // Simulate the voting process
    while (radiant.length > 0 && dire.length > 0) {
        // Check which senator is next in line
        if (radiant[0] < dire[0]) {
            // Radiant senator bans the next Dire senator
            dire.shift(); // Remove the next Dire senator
            // Radiant senator is added back to the queue, with updated index
            radiant.push(radiant.shift()! + n); //Add the radiant senator to the end of the queue.
        } else {
            // Dire senator bans the next Radiant senator
            radiant.shift(); // Remove the next Radiant senator
            // Dire senator is added back to the queue, with updated index
            dire.push(dire.shift()! + n); //Add the dire senator to the end of the queue.
        }
    }

    // Determine the winner based on which queue is not empty
    return radiant.length > 0 ? "Radiant" : "Dire";
}

🔵Go

func predictPartyVictory(senate string) string {
    // Queues to store the indices of Radiant and Dire senators
    radiant := []int{}
    dire := []int{}
    n := len(senate) // Length of the senate string

    // Populate the queues with senator indices
    for i, s := range senate {
        if s == 'R' {
            radiant = append(radiant, i)
        } else {
            dire = append(dire, i)
        }
    }

    // Simulate the voting process
    for len(radiant) > 0 && len(dire) > 0 {
        // Check which senator is next in line
        if radiant[0] < dire[0] {
            // Radiant senator bans the next Dire senator
            dire = dire[1:] // Remove the next Dire senator
            // Radiant senator is added back to the queue, with updated index
            radiant = append(radiant, radiant[0]+n) // Add the radiant senator to the end of the queue.
            radiant = radiant[1:] //remove the first radiant senator.
        } else {
            // Dire senator bans the next Radiant senator
            radiant = radiant[1:] // Remove the next Radiant senator
            // Dire senator is added back to the queue, with updated index
            dire = append(dire, dire[0]+n) // Add the dire senator to the end of the queue.
            dire = dire[1:] // remove the first dire senator.
        }
    }

    // Determine the winner based on which queue is not empty
    if len(radiant) > 0 {
        return "Radiant"
    }
    return "Dire"
}

If you liked this article I’d appreciate an upvote or a comment. That helps me improve the quality of my posts as well as getting to know more about you, my dear reader.

Muchas gracias!

Follow me for more content like this.

Down below you can find other ways to tip my work.

BankTransfer: "710969000019398639", // CLABE
BAT: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
ETH: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
BTC: "33xxUWU5kjcPk1Kr9ucn9tQXd2DbQ1b9tE",
ADA: "addr1q9l3y73e82hhwfr49eu0fkjw34w9s406wnln7rk9m4ky5fag8akgnwf3y4r2uzqf00rw0pvsucql0pqkzag5n450facq8vwr5e",
DOT: "1rRDzfMLPi88RixTeVc2beA5h2Q3z1K1Uk3kqqyej7nWPNf",
DOGE: "DRph8GEwGccvBWCe4wEQsWsTvQvsEH4QKH",
DAI: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875"

DSA (Medium) — Queue — Dota2 Senate

Explanation

Pseudocode

Implementation

🐍Python

🟡Typescript

🔵Go