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:

submissions open for another day (since the last time I edited the post)

  • nieceandtows@programming.dev
    1·
    1 year ago

    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 &lt; 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])