Programming Challenges

Here's my Python solution. If my reasoning is all correct, it should (in theory) run in O(n * (number of matches)), which should be optimal since it takes at least that long to print out the results anyway. IF my reasoning is all correct, and my program is all correct.

closing_to_opening = {')': '(', ']': '[', '}': '{'}

def main(n: int) -> list[str]:
    assert n % 2 == 0, f'n must be even; got {n=}'
    acc: list = [(n // 2, None, None)]
    for i in range(n):
        new_acc = []
        for closing_brackets_left, unmatched_series, full_series in acc:
            if unmatched_series is not None:
                most_recent_closing_bracket, rest = unmatched_series
                matching_opening_bracket = closing_to_opening[most_recent_closing_bracket]
                new_acc.append((closing_brackets_left, rest, (matching_opening_bracket, full_series)))
            if closing_brackets_left > 0:
                for bracket in [')', ']', '}']:
                    new_acc.append((closing_brackets_left - 1, (bracket, unmatched_series), (bracket, full_series)))
        acc = new_acc
    result = []
    for _, _, series in acc:
        series_as_list = []
        for _ in range(n):
            bracket, series = series
            series_as_list.append(bracket)
        result.append(''.join(series_as_list))
    return result

if __name__ == '__main__':
    from argparse import ArgumentParser
    parser = ArgumentParser()
    parser.add_argument('n')
    result = main(int(parser.parse_args().n))
    print('\n'.join(result))

Idea: The matches of size n are precisely the strings with n/2 closing brackets, n/2 opening brackets, and brackets arranged so that each closing bracket matches up with the opening bracket on the "top of the stack" when processing the string and removing matches. We build the strings backwards. For each match-in-construction, we track the number of closing brackets left to be added, the "stack" (but working backwards, so the roles of opening and closing brackets are reversed), and, of course, the actual string. We transform each match-in-construction into 1, 3, or 4 new matches-in-construction, adding one character at a time: the opening bracket that matches the closing bracket on the top of the stack (if any), and the three closing brackets (if we still have closing brackets to add). Because appending to strings is O(n) since we need to copy, and pushing and popping from Python lists creates mutable aliasing issues (and would take O(n) to copy, just like with strings), we do a Lisp and use cons cells to create lists instead (hence, the backwards building). I suspect it gives the same asymptotic runtime anyway, but I don't actually know whether that's true.