Dota2 Senate

Intuition

Solution

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        R = []
        D = []
        for i in range(len(senate)):
            if senate[i] == 'R':
                R.append(i)
            else:
                D.append(i)
        if self.helper(R, D):
            return 'Radiant'
        else:
            return 'Dire'

    def helper(self, R, D):
        if not D:
            return True
        elif not R:
            return False

        Di, Ri = 0, 0
        D2, R2 = [], []
        D2i, R2i = 0, 0
        while Di < len(D) or Ri < len(R):
            if Di == len(D):
                R2.append(R[Ri])
                Ri += 1
                D2i += 1
            elif Ri == len(R):
                D2.append(D[Di])
                Di += 1
                R2i += 1
            elif R[Ri] < D[Di]:
                R2.append(R[Ri])
                Ri += 1
                Di += 1
            else:
                D2.append(D[Di])
                Di += 1
                Ri += 1
        return self.helper(R2[R2i:], D2[D2i:])