Brackets

Good day! In this post we will attempt to solve the Brackets problem from Codility_.

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

o S is empty;
o S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
o S has the form "VW" where V and W are properly nested strings.

For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function such that given a string S consisting of N characters, 
returns 1 if S is properly nested and 0 otherwise.

Write an efficient algorithm for the following assumptions:

o N is an integer within the range [0..200,000];
o string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".

We are presented with a string. We need to determine if the different types of brackets match. If interested in this problem I suggest you read the current and full description at Codility_.

We will be solving this problem using the Java programming language and the VSCode IDE on a Windows computer. We will not be using the on-line IDE provided by Codility_.

public int brackets(String S) {
}

The signature for the function of interest indicates that we are provided a single string argument. We need to return 1 if the string is properly balanced or 0 indicating it is not.

{[()()]}
main <<< s ==>{[()()]}<==
main <<< result: 1


([)()]
main <<< s ==>([)()]<==
main <<< result: 0


((([](){}
main <<< s ==>((([](){}<==
main <<< result: 0


)(
main <<< s ==>)(<==
main <<< result: 0



main <<< s ==><==
main <<< result: 1

We will be developing a test scaffold to test the code. This is required because we will not be solving the problem using the online IDE provided by Codility_. Note that the test code IS NOT PART OF THE SOLUTION.

Each test case starts with an input line that we will use to populate the string argument to the function of interest. The string is displayed by our test code to make sure all is well before calling the function of interest. The function of interest is then called and the result displayed.

    /**
     * Test scaffold.
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read string ****
        String s = br.readLine().trim();

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< s ==>" + s + "<==");

        // **** call function of interest and display result ****
        System.out.println("main <<< result: " + brackets(s));
    }

Our test code is quite simple and matches the description of processing a test case. I believe we do not have much to add at this time.

    /**
     * Given a string S consisting of N characters, 
     * returns 1 if S is properly nested and 0 otherwise.
     * 
     * Execution: O(n) - Space: O(1)
     */
    static public int brackets(String s) {

        // **** sanity checks ****
        if (s == null) return 0;
        if (s.length() == 0) return 1;

        // **** initialization ****
        Stack<Character> stack = new Stack<>();

        // **** traverse string looking for unmatched brackets ****
        for (char ch : s.toCharArray()) {

            // **** proceed based on current character - O(n) ****
            if (ch == '(' || ch == '[' || ch == '{')
                stack.push(ch);
            else {

                // **** check if stack is empty ****
                if (stack.size() == 0) return 0;

                // **** validate character ****
                if (ch == ')') {
                    if (stack.pop() != '(') return 0;
                } else if (ch == ']') {
                    if (stack.pop() != '[') return 0;
                } else if (ch == '}') {
                    if (stack.pop() != '{') return 0;
                } else
                    return 0;
            }
        }

        // **** check stack contents ****
        if (stack.size() != 0) return 0;

        // **** string is valid ****
        return 1;
    }

Our function of interest starts by performing some sanity checks.

We then initialize a stack. The idea is to push all opening brackets. When we encounter a closing bracket we check by popping the top of the stack and comparing if the opening bracket matches the closing one. If they do not we return a failure code.

Note that if a closing bracket is encountered and the stack is empty we need to check such conditions. We do so by checking if the size of the stack is 0.

After the loop we need to check if there are characters left in the stack. That would imply that some opening brackets were not closed so the string is invalid.

If all is well when all is said and done, our function returns 1 to indicate that all brackets match.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode).

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.

Thanks for reading this post, feel free to connect with me John Canessa  LinkedIn.

Enjoy;

John