Dota2 Senate

Medium
393.

Dota2 Senate

Dota2 Senate is a medium coding problem on strings, greedy and queue, asked in Amazon and Microsoft interviews.

The senate has senators from the Radiant and Dire parties, given as a string of 'R' and 'D' in seating order. Voting proceeds in rounds; in each round every remaining senator, in order, may either ban one senator from the other party for the rest of the game, or — if only their own party remains — declare victory.

Assuming every senator plays optimally, return the winning party: "Radiant" or "Dire".

Example 1

Input
senate = "RD"
Output
Radiant

Example 2

Input
senate = "RDD"
Output
Dire

Example 3

Input
senate = "DRRDRDRDRDDRDRDR"
Output
Radiant

Constraints

  • 1 <= senate.length <= 40
  • senate consists of 'R' and 'D'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} senate
 * @return {string}
 */
var predictPartyVictory = function(senate) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Dota2 Senate — Solution in Python, Java & C++

Dota2 Senate solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on strings and greedy.

Dota2 Senate is a medium coding problem on strings, greedy and queue, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy, Queue
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The senate has senators from the Radiant and Dire parties, given as a string of 'R' and 'D' in seating order. Voting proceeds in rounds; in each round every remaining senator, in order, may either ban one senator from the other party for the rest of the game, or — if only their own party remains — declare victory.

Assuming every senator plays optimally, return the winning party: "Radiant" or "Dire".

Example 1

Input: senate = "RD"
Output: Radiant

Example 2

Input: senate = "RDD"
Output: Dire

Example 3

Input: senate = "DRRDRDRDRDDRDRDR"
Output: Radiant

Constraints

  • 1 <= senate.length <= 40
  • senate consists of 'R' and 'D'.

Hints for Dota2 Senate

  1. Hint 1

    A senator's best move is always to ban the next opposing senator who would otherwise act.

  2. Hint 2

    Keep two queues of indices, one per party, and pop the front of each.

  3. Hint 3

    Whoever has the smaller index bans the other and rejoins the queue with index i + n, representing the next round.

How to solve Dota2 Senate

A senator's best move is to ban the next opposing senator in turn order. Keep a queue of indices per party; the smaller index bans the other and rejoins with index + n for the next round.

Approach

  1. Fill two queues with the indices of R and D.
  2. While both are non-empty, pop one from each; the smaller index survives and is re-pushed as i + n.
  3. Return the party with senators left.

Why it works

Banning the nearest upcoming opponent removes the most imminent threat, and adding n preserves round order so the simulation is exact.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Re-pushing without the + n offset breaks the round ordering.

Reference solution

Python

from collections import deque

def predictPartyVictory(senate: str) -> str:
    n = len(senate)
    radiant = deque(i for i, ch in enumerate(senate) if ch == "R")
    dire = deque(i for i, ch in enumerate(senate) if ch == "D")
    while radiant and dire:
        r = radiant.popleft()
        d = dire.popleft()
        if r < d:
            radiant.append(r + n)
        else:
            dire.append(d + n)
    return "Radiant" if radiant else "Dire"

Java

public static String predictPartyVictory(String senate) {
    int n = senate.length();
    List<Integer> radiant = new ArrayList<>();
    List<Integer> dire = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (senate.charAt(i) == 'R') radiant.add(i);
        else dire.add(i);
    }
    int r = 0, d = 0;
    while (r < radiant.size() && d < dire.size()) {
        int ri = radiant.get(r++);
        int di = dire.get(d++);
        if (ri < di) radiant.add(ri + n);
        else dire.add(di + n);
    }
    return r < radiant.size() ? "Radiant" : "Dire";
}

C++

string predictPartyVictory(string senate) {
    int n = (int) senate.size();
    vector<int> radiant, dire;
    for (int i = 0; i < n; i++) {
        if (senate[i] == 'R') radiant.push_back(i);
        else dire.push_back(i);
    }
    size_t r = 0, d = 0;
    while (r < radiant.size() && d < dire.size()) {
        int ri = radiant[r++];
        int di = dire[d++];
        if (ri < di) radiant.push_back(ri + n);
        else dire.push_back(di + n);
    }
    return r < radiant.size() ? "Radiant" : "Dire";
}

JavaScript

var predictPartyVictory = function(senate) {
    const n = senate.length;
    const radiant = [], dire = [];
    for (let i = 0; i < n; i++) {
        if (senate.charAt(i) === "R") radiant.push(i);
        else dire.push(i);
    }
    let r = 0, d = 0;
    while (r < radiant.length && d < dire.length) {
        const ri = radiant[r++];
        const di = dire[d++];
        if (ri < di) radiant.push(ri + n);
        else dire.push(di + n);
    }
    return r < radiant.length ? "Radiant" : "Dire";
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms