Council of Two Clans

Medium

A council has members from two clans: R (the Radiant clan) and D (the Dire clan). The string council gives the order in which they sit around the table. Voting goes in rounds. In each round, members take turns starting from the first one; anyone who has lost their vote is skipped. On their turn, a member may: - strip any member of the other clan of their vote, for good; - declare victory for their clan, if everyone who still has a vote belongs to it. Everyone plays optimally for their own clan. Return "Radiant" or "Dire": the clan that declares victory.

Example 1

council="DR" → 'Dire'

The D member moves first and strips the only R of their vote. Only D remains, so "Dire" wins.

Example 2

council="RRDDD" → 'Radiant'

In round one the two Rs remove two Ds, and the remaining D removes the first R. In round two the second R removes the last D, so "Radiant" wins.

Example 3

council="DRRD" → 'Dire'

Constraints

1 ≤ len(council) ≤ 10⁵
council[i] is 'R' or 'D'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Queue String

Similar problems

Biggest Number From Pieces Medium Every Letter Once Medium Erase Digits for the Smallest Number Medium Smallest Up-Down Sequence Medium Ring of Flippable Words Medium

Input

council="DR"

Expected

'Dire'

Run checks the first 3 tests in your browser. Submit checks all 169 tests on the server, hidden ones included.