68ms Python Solution

• The senate string can be winded up as a circle.

For each senator, the best choice is to ban the first opponent who is able to vote in the future.

The solution uses `banned_d` and `banned_r` to record how many d-senator / r-senator will be banned.

When it comes to a senator to vote, say it's a d-sanator:

• if `banned_d == 0` (no d-senator will be banned), this d-senator bans an opponent (`banned_r += 1`) and stays in the senate to the next round.
• otherwise (`banned_d > 0`), this d-senator is sacrificed and `banned_d` head count becomes smaller.

Once the senate has no r-senators, "Dire" wins. And vice versa.

``````  def predictPartyVictory(self, s):
banned_d = banned_r = 0
while True:
s2 = []
has_d = has_r = False
for c in s:
if c == 'R':
if banned_r == 0:
s2.append('R')
has_r = True
banned_d += 1
else:
banned_r -= 1
else:
if banned_d == 0:
s2.append('D')
has_d = True
banned_r += 1
else:
banned_d -= 1
if not has_r: return 'Dire'
s = s2
``````

• Same idea - update the string, but with a different way to terminate:
when one party is twice outnumbering the other at the end of the round (same as at the start), then this party will win.

``````from collections import Counter
class Solution(object):
def predictPartyVictory(self, senate):
"""
:type senate: str
:rtype: str
"""
ban = Counter()
while senate:
new = ""
for i in senate:
if ban[ i ] > 0:
ban[ i ] -= 1
else:
new += i
ban[ chr(150-ord(i)) ] += 1
for c in 'RD':
if new.count(c) > new.count(chr(150-ord(c))) * 2:
return res[c]
senate = new
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.