Given some assortment of brackets, you must find the largest substring that is a valid matching bracket pattern
- A bracket match is an opening and closing version of the same kind of bracket beside each other ()
- If a bracket matches then outer brackets can also match (())
- The valid brackets are ()[]{}
For example for the input {([])()[(])}()]
the answer would be ([])()
as that is the largest substring that has all matches
You must accept the input as a command line argument (entered when your app is ran) and print out the result
(It will be called like node main.js [(]()
or however else to run apps in your language)
You can use the solution tester in this post to test you followed the correct format https://programming.dev/post/1805174
Any programming language may be used. 3 points will be given if you pass all the test cases with 1 bonus point going to whoevers performs the quickest and 1 for whoever can get the least amount of characters
To submit put the code and the language you used below
People who completed the challenge:
- @[email protected] -
6.64s
-1203 chars
(rust) - @[email protected] -
0.148s
-1251 chars
(python) - @[email protected] -
0.008s
-1268 chars
(python) - @[email protected] -
0.001s
-1516 chars
(c) (fastest) - @[email protected]
0.031s
-317 chars
(javascript) (shortest)
submissions open for another day (since the last time I edited the post)
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’.