Dota2 Senate

Dota2 Senate is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Task Scheduling (Frequency Based) subpattern.

Problem statement

Implement Solution.predictPartyVictory, which receives senate, a non-empty string describing senators arranged in a circle. Each character is one senator: R belongs to the Radiant party and D belongs to the Dire party. The characters' order determines the order in which senators act, starting with the first character.

When an active senator takes a turn, that senator may permanently ban one active senator from the opposing party. A banned senator loses the right to act and vote, while the senator who performed the ban remains active. After the final position in senate is processed, continue again from the first position, skipping banned senators.

Continue until every active senator belongs to the same party. Return exactly "Radiant" if Radiant remains, or exactly "Dire" if Dire remains.

Example 1:

Input: senate = "DRR" Output: "Radiant" Explanation: The first Dire senator bans one Radiant senator, but the remaining Radiant senator later bans that Dire senator. Radiant is the only party left.

Example 2:

Input: senate = "RDDR" Output: "Radiant" Explanation: The first Radiant senator removes the next Dire senator, and the later turns allow Radiant to eliminate the remaining Dire senator before losing its own active senators.

Example 3:

Input: senate = "DDRRR" Output: "Dire" Explanation: The two Dire senators can successively remove two Radiant senators, and the remaining exchanges leave Dire with an active senator while all Radiant senators are banned.

Constraints:

- 1 <= senate.length <= 10^5 - Every character in senate is either R or D. - The senators are processed in the circular order represented by senate. - A senator can ban at most one opposing senator per turn. - A banned senator cannot act or vote on any later turn.

Topics and companies

Topics: Greedy, Queue, Simulation, String.

How to practise Dota2 Senate on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.

Open Dota2 Senate in the code editor, or read the Dota2 Senate editorial for a worked solution with its approach and complexity analysis.

Where Dota2 Senate sits in the DSA pattern sheet

Problems related to Dota2 Senate

Other problems that use the same Task Scheduling (Frequency Based) and Greedy Patterns techniques:

Preparing this workspace.