Take-Turns Voting Game

medium queue greedy

Problem

A row of senators belongs to one of two parties, R or D. They vote in order; on each turn, the current senator may ban the very next opposing senator. Banned senators skip every future round. The party that survives wins. Maintain two queues of upcoming move indices and pop the earlier each round; the winner re-enters at index + n.

Inputsenate = "RDD"

Output"D"

R bans D[1]; D[2] then bans R[0]; D wins.

senate (R/D string)

from collections import deque
def predict_winner(s):
    r, d = deque(), deque()
    n = len(s)
    for i, c in enumerate(s):
        (r if c == 'R' else d).append(i)
    while r and d:
        ri, di = r.popleft(), d.popleft()
        if ri < di: r.append(ri + n)
        else: d.append(di + n)
    return "R" if r else "D"

function predictWinner(s) {
  const r = [], d = [], n = s.length;
  for (let i = 0; i < n; i++) (s[i] === 'R' ? r : d).push(i);
  while (r.length && d.length) {
    const ri = r.shift(), di = d.shift();
    if (ri < di) r.push(ri + n); else d.push(di + n);
  }
  return r.length ? "R" : "D";
}

class Solution {
    public String predictWinner(String s) {
        Deque<Integer> r = new ArrayDeque<>(), d = new ArrayDeque<>();
        int n = s.length();
        for (int i = 0; i < n; i++) (s.charAt(i) == 'R' ? r : d).offer(i);
        while (!r.isEmpty() && !d.isEmpty()) {
            int ri = r.poll(), di = d.poll();
            if (ri < di) r.offer(ri + n); else d.offer(di + n);
        }
        return !r.isEmpty() ? "R" : "D";
    }
}

string predictWinner(string s) {
    queue<int> r, d;
    int n = s.size();
    for (int i = 0; i < n; i++) (s[i] == 'R' ? r : d).push(i);
    while (!r.empty() && !d.empty()) {
        int ri = r.front(); r.pop();
        int di = d.front(); d.pop();
        if (ri < di) r.push(ri + n); else d.push(di + n);
    }
    return !r.empty() ? "R" : "D";
}

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