Rust: https://pastebin.com/frYcgdxh

Like last time, a brute force solution: checking if every substring is a set of well formed brackets, and, if so, recording it if its the longest seen so far.

I found this one easier than the medium as well. Maybe because I actually know a strategy for this one. Anywho, solution is in JavaScript. It’s super ugly as I went for lowest character count, so no declarations, single char variable names, no semicolons, etc…

Basically use a anchor-runner pointer strategy to find a correct substring, I use a stack based solution for checking if the substring is correct. When the stack is empty, the substring is good, thus I record the start of it and its length. If, I get another good point, I just record the highest. If I hit a point where its no longer good, I jump the start to the end of the most recent good substring. Pretty fun.

Formatting screwed mine up, so heres a pastbin

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 
#include 
#include 
#include 

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);
}

Rust solution:

use std::cmp::min;
use std::ops::Range;

fn completer(bracket: char) -> char {
    match bracket {
        ')' => '(',
        '}' => '{',
        ']' => '[',
        _ => unreachable!(),
    }
}

pub struct Char {
    index: usize,
    value: char,
}

fn main() {
    let input: String = std::env::args().nth(1).unwrap();
    let mut longest = Range::default();
    {
        let mut current = Range::default();
        let mut stack: Vec = Vec::with_capacity(input.len() << 1);
        let mut streak = false;
        for (i, c) in input.chars().enumerate() {
            match c {
                ']' | '}' | ')' => {
                    let matched = stack
                        .last()
                        .map(|other| completer(c) == other.value)
                        .unwrap_or_default();
                    if matched {
                        current.start = if streak {
                            min(current.start, stack.pop().unwrap().index)
                        } else {
                            stack.pop().unwrap().index
                        };
                        current.end = i;
                        streak = true;
                    } else {
                        stack.clear();
                        if longest.len() < current.len() {
                            longest = current;
                        }
                        current = Range {
                            start: i + 1,
                            end: i + 1,
                        };
                        streak = false;
                    }
                }
                '[' | '{' | '(' => {
                    stack.push(Char { index: i, value: c });
                }
                _ => {}
            };
        }

        if streak {
            longest = current;
        }
    }

    if longest.start != longest.end {
        longest.end += 1;
    }
    println!("{}", &input[longest]);
}

Also available at: https://pastebin.com/EJsLYPqQ

This is interesting, though I am 3 weeks late.

Raku code: https://glot.io/snippets/gonclpwl3p