Programming Challenges

I actually found this challenge to be easier than this week's medium challenge. (Watch me say that and get this wrong while also getting the medium one correct...) Here's an O(n) solution:

bracket_pairs = {('(', ')'), ('[', ']'), ('{', '}')}

def main(brackets: str) -> str:
    n = len(brackets)
    has_match_at = {i: False for i in range(-1, n + 1)}
    acc = []
    for i, bracket in enumerate(brackets):
        acc.append((i, bracket))
        if len(acc) >= 2:
            opening_idx, opening = acc[-2]
            closing_idx, closing = acc[-1]
            if (opening, closing) in bracket_pairs:
                acc.pop(), acc.pop()
                has_match_at[opening_idx] = has_match_at[closing_idx] = True
    longest_start, longest_end = 0, 0
    most_recent_start = None
    for left_idx, right_idx in zip(range(-1, n), range(0, n + 1)):
        has_match_left = has_match_at[left_idx]
        has_match_right = has_match_at[right_idx]
        if (has_match_left, has_match_right) == (False, True):
            most_recent_start = right_idx
        if (has_match_left, has_match_right) == (True, False):
            most_recent_end = right_idx
            if most_recent_end - most_recent_start > longest_end - longest_start:
                longest_start, longest_end = most_recent_start, most_recent_end
    return brackets[longest_start:longest_end]

if __name__ == '__main__':
    from argparse import ArgumentParser
    parser = ArgumentParser()
    parser.add_argument('brackets')
    print(main(parser.parse_args().brackets))

We start off by doing the same thing as this week's easy challenge, except we keep track of the indices of all of the matched brackets that we remove (opening or closing). We then identify the longest stretch of consecutive removed-bracket indices, and use that information to slice into the input to get the output.

For ease of implementation of the second part, I modelled the removed-bracket indices with a dict simulating a list indexed by [-1 .. n + 1), with the values indicating whether the index corresponds to a matched bracket. The extra elements on both ends are always set to False. For example, {([])()[(])}()] -> FFTTTTTTFFFFFTTFF, and ([{}]) -> FTTTTTTF. To identify stretches of consecutive indices, we can simply watch for when the value switches from False to True (start of a stretch), and from True to False (end of a stretch). We do that by pairwise-looping through the dict-list, looking for 'FT' and 'TF'.