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)

  • lavafroth
    link
    fedilink
    arrow-up
    1
    ·
    1 year ago

    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

      • lavafroth
        link
        fedilink
        arrow-up
        1
        ·
        1 year ago

        lol forgot the cases where there might be multiple nested braces!