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)
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
4/6 test cases passed
lol forgot the cases where there might be multiple nested braces!