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:
- @SleveMcDichael@programming.dev -
6.64s
-1203 chars
(rust) - @shape-warrior-t@kbin.social -
0.148s
-1251 chars
(python) - @nieceandtows@programming.dev -
0.008s
-1268 chars
(python) - @brie@beehaw.org -
0.001s
-1516 chars
(c) (fastest) - @Quasari@programming.dev
0.031s
-317 chars
(javascript) (shortest)
submissions open for another day (since the last time I edited the post)
Please feel free to suggest changes to make the code more efficient.
EDIT: for some reason, < is not showing up properly inside a code block. Kindly replace it with the right symbol when you test.
Python:
import sys
input_string = sys.argv[1]
matches = {
"}": "{",
"]": "[",
")": "("
}
bracket_matches_strict = []
def get_matching_substring_strict(string):
substring = ''
index_start = -1
index_end = -1
bracket_counts = {
"{": 0,
"[": 0,
"(": 0
}
for index, letter in enumerate(string):
if letter in matches.values():
if index_start == -1:
index_start = index
substring += letter
bracket_counts[letter] += 1
if letter in matches.keys():
if not substring:
break
if substring[-1] == matches[letter]:
substring = substring[:-1]
bracket_counts[matches[letter]] -= 1
if not [cnt for cnt in bracket_counts.values() if cnt]:
index_end = index
if [cnt for cnt in bracket_counts.values() if cnt < 0]:
break
else:
break
if index_start != -1 and index_end != -1:
matching_substring = string[index_start:index_end + 1]
return len(matching_substring), matching_substring
for i in range(len(input_string)):
bracket_substring_strict = get_matching_substring_strict(input_string[i:])
if bracket_substring_strict:
bracket_matches_strict.append(bracket_substring_strict)
print(sorted(bracket_matches_strict)[-1][1])