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)

  •  brie   ( @brie@beehaw.org ) 
    link
    fedilink
    English
    21 year ago

    C: gcc -O2 hard.c

    This is very poorly written, but does seem to work.

    The stack keeps track of the start of a match, and the character that would complete the match. In cases where a match just ended, the start is preserved (because two adjacent matches are effectively one), but the required matching character is changed to that of the new opening match.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stddef.h>
    
    int main(int argc, char **argv)
    {
    	char map[256] = { 0 };
    	struct match {
    		char const *start;
    		char requirement;
    	};
    	char const *match_start;
    	ptrdiff_t length = 0;
    	char const *p;
    	struct match *stack, *top;
    	char opener;
    
    	if (argc != 2) {
    		fputs("Improper invocation\n", stderr);
    		exit(EXIT_FAILURE);
    	}
    
    	/* Initialise lookup table */
    	map[')'] = '(';
    	map[']'] = '[';
    	map['}'] = '{';
    
    	if (!(stack = calloc(sizeof(*stack), strlen(argv[1]) + 1))) {
    		fputs("Allocation failure\n", stderr);
    		exit(EXIT_FAILURE);
    	}
    	/* Note: stack[0].requirement must be 0. This is satisfied by calloc. */
    	top = stack;
    
    	match_start = argv[1];
    	for (p = argv[1]; *p; p++) {
    		/* Are we a closing brace? */
    		if ((opener = map[(size_t)*p])) { /* Yes */
    			if (top->requirement == opener) {
    				if (p - top->start >= length) {
    					length = p - top->start + 1;
    					match_start = top->start;
    				}
    				top[1].start = 0;
    				top--;
    			} else {
    				top[1].start = 0;
    				/* Set start to nullptr to invalidate the matches */
    				while (top > stack) {
    					top--->start = 0;
    				}
    			}
    		} else { /* No */
    			(++top)->requirement = *p;
    			/* If we are right outside another match, we can use their pointer instead */
    			if (!top->start) {
    				top->start = p;
    			}
    		}
    	}
    
    	printf("%.*s\n", (int)length, match_start);
    
    	free(stack);
    }