Balanced Brackets HackerRank Solution in Java and Python with Explanation

Java and Python Solution for Balanced Brackets HackerRank Problem | Check opening and closing brackets match or not

Problem Description :

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].

Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].

By this logic, we say a sequence of brackets is balanced if the following conditions are met:

1. It contains no unmatched brackets.
2. The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.

Given n Strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, return YES. Otherwise, return NO. 

Example 1 :

input : "{[()]}"
output : YES

Example 2 :

input : "{[(])}"
output : NO

Example 3 :

input : "{{[[(())]]}}"
output : YES

Example 4 :

input : "}][}}(}]{))]"
output : NO

So lets jump on code. First we will seen code in Java and then Python.

Solution 1 : Balanced Brackets Solution in Java

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    public static String isBalanced(String s) {

        // Convert string to character array
        char[] array = s.toCharArray();
        
        List<Character> list = new ArrayList<>();

        // Return "NO" if starting bracket is closing bracket
        if (array[0] == ')' || array[0] == '}' || array[0] == ']') {
            return "NO";
        }
        
        for (int i = 0; i < array.length; i++) {
            if (array[i] != ')' && array[i] != '}' && array[i] != ']') {
                list.add(array[i]);
            } else if (list.size() == 0) {
                return "NO";
            } else {
                char lastBreacket = list.get(list.size()-1);
                if (lastBreacket == '(' && array[i] != ')') {
                    return "NO";
                } else if (lastBreacket == '{' && array[i] != '}') {
                     return "NO";
                } else if (lastBreacket == '[' && array[i] != ']') {
                     return "NO";
                } else {
                    list.remove(list.size()-1);
                }
            }
        }

        if (list.size() == 0) {
            return "YES";
        } else {
            return "NO";
        }
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, t).forEach(tItr -> {
            try {
                String s = bufferedReader.readLine();

                String result = Result.isBalanced(s);

                bufferedWriter.write(result);
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Solution Explanation :

• Convert given string to character array.
• If first character is closing bracket, then return "NO". (No need to go forward).
• Traverse through character array.
• If current bracket does not start with closing brackets, then store into characters list.
• In else if condition, return "NO" if list size becomes 0 and array still contains brackets.
• In else condition, get last bracket from list and check current array bracket match its closing brackets or not. If it is match then remove last bracket from list otherwise return "NO".
• After for loop, return "YES" if list size is 0 otherwise return "NO".

Solution 2 : Balanced Brackets Solution in Python

def isBalanced(s):
    stack = []
    # map right bracket (key) to left bracket (value)
    right = {'}':'{',')':'(',']':'['}
    left = ['(','{','[']
    for c in s:
        # push all left brackets to the stack
        if c in left:
            stack.append(c)
        else:
            if len(stack) > 0 and stack[-1] == right[c]:
                # matches
                stack.pop()
            else:
                # doesn't match
                return 'NO'
    # if anything is still on the stack
    if len(stack) > 0:
        return 'NO'
    # made it through all tests
    return 'YES'

Solution Explanation :

• Whenever an opening bracket appears, we push it onto the stack.
• If a closing bracket appears and if it matches the opening bracket at the top of the stack, it means that the brackets are balanced and we pop the opening bracket out of the stack and continue analyzing the string.
• If the closing bracket doesn't match the opening bracket at the top of the stack, we can infer that the string is not balanced, and we print NO.
• After processing the string completely and if the stack is empty, the string is balanced, and we print YES, else, we print NO.

Other HackerRank Problem and Solution with Explanation :

• Recursive Digit Sum HackerRank solution in Java with Explanation 
• Jumping on the Clouds HackerRank Java Solution