Bulb Switcher II

Intuition

Solution

class Solution:
    def flipLights(self, n: int, m: int) -> int:
        if n >= 5:
            n = 4
        states = set()
        states.add('o' * n)
        index = 0
        while index < m:
            n = set()
            for s in states:
                tmp = ''
                for i in range(len(s)):
                    if i % 2 == 0:
                        tmp += 'o' if s[i] == 'x' else 'x'
                    else:
                        tmp += s[i]
                n.add(tmp)
                tmp = ''
                for i in range(len(s)):
                    if i % 2 == 1:
                        tmp += 'o' if s[i] == 'x' else 'x'
                    else:
                        tmp += s[i]
                n.add(tmp)
                tmp = ''
                for i in range(len(s)):
                    if i % 3 == 0:
                        tmp += 'o' if s[i] == 'x' else 'x'
                    else:
                        tmp += s[i]
                n.add(tmp)
                tmp = ''
                for i in range(len(s)):
                    tmp += 'o' if s[i] == 'x' else 'x'
                n.add(tmp)
            states = n
            index += 1
            if len(states) == 8:
                return 8
        return len(states)