class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        q = list(senate)
        while len(q)>0:
            cur = q.pop(0)
            opp = "R" if cur is "D" else "D"
            if len(q)>0 and self.contain_opposite(cur, q):
                q.remove(opp)
                q.append(cur)
            else:
                return "Radiant" if cur is "R" else "Dire"
    def contain_opposite(self, s, q):
        if len(q) is 0:
            return False
        if len(set(q))>1:
            return True
        return q[0] is not s

優化時間複雜度

使用兩個 queue，一個保存 R 隊的 index，另一個保存 D 隊的 index

然後兩隊 queue 最上面那個持續對抗，每一輪各派一個，index小的獲勝，勝利方在queue後面push進去最新的 index（表示該議員下一輪的 index）

直到兩個 queue 有一個為空，判斷結果

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        radiant_q, dire_q = [], []
        senate_list = list(senate)
        for i in range(len(senate_list)):
            if senate_list[i] is "R":
                radiant_q.append(i)
            else:
                dire_q.append(i)
        next_round = len(senate)
        while radiant_q and dire_q:
            if radiant_q[0] < dire_q[0]:
                radiant_q.append(next_round)
            else:
                dire_q.append(next_round)
            next_round += 1
            radiant_q.pop(0)
            dire_q.pop(0)
        return "Radiant" if radiant_q else "Dire"

TC, SC = O(n)