Problem statement

https://binarysearch.com/problems/Candy-Race-with-Different-Types/

Solution

Variation of Leetcode 1047. Remove All Adjacent Duplicates In String - in fact we just need to check how many steps we can make: it can be proved that it is always the same.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        stack, ans = [], 0
        for symb in s:
            if stack and stack[-1] == symb:
                stack.pop()
                ans += 1
            else:
                stack.append(symb)
        return ans % 2 == 1