Problem statement

https://binarysearch.com/problems/Overchoice/

Solution

Equal to Leetcode 1087 Brace Expansion.

Complexity

Time complexity to create t is O(n), but then we need to create answer as well. Potentially it can be upto O(2^(n/5)) for the case with two letters in each brackets.

Code

class Solution:
    def solve(self, s):
        t = []
        parts = s.replace("[", "]").split("]")
        for part in parts:
            if not part: continue
            t.append(sorted(part.split("|")))

        return ["".join(x) for x in product(*t)]