649.md

649. Dota2 Senate

Solution 1 (time O(n), space O(n))

# Greedy
class Solution(object):
    def predictPartyVictory(self, senate):
        """
        :type senate: str
        :rtype: str
        """
        n = len(senate)
        qr = collections.deque([i for i, c in enumerate(senate) if c == "R"])
        qd = collections.deque([i for i, c in enumerate(senate) if c == "D"])
        while qr and qd:
            if qr[0] < qd[0]:
                qd.popleft()
                qr.append(qr.popleft() + n)
            else:
                qr.popleft()
                qd.append(qd.popleft() + n)
        return "Radiant" if qr else "Dire"