Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Balanced parenthesis challenge

Sharing is caring!

Problem statement
Create function that will determine if the parenthesis are balanced in a given string s.

Sample Input 1

(kjds(hfkj)sdhf

Sample Output 1

false

Sample Input 2

a(bcd)d

Sample Output 2

true

Solution
We will iterate over the string’s characters and hold three counters: openParentheses, openSquare and openCurly that will refer to the number of open (, [ and { parentheses. Each time we encounter a (, [ or {, we increment openParentheses, openSquare or openCurly respectively. Similarly, each time we encounter a ), ] or }, we decrement openParentheses, openSquare or openCurly respectively. If at any point during our iteration, openParentheses, openSquare or openCurly is \textless 0, we know that we have closed more parentheses than we have opened. In that case we return false. If that is not the case and we have finished iterating over all characters we check whether openParentheses, openSquare or openCurly is \textgreater 0. In case one of our counters is \textgreater 0, we return false since we have opened more parentheses than we have closed. If non of the above is the case, we can return true since our parentheses are balanced.

The coded solution is listed below.

Full code

public class ValidParenthesesInString {
    private static boolean validate(String str) {
        boolean result = true;

        int openParentheses = 0;
        int openSquare = 0;
        int openCurly = 0;

        for (char c : str.toCharArray()) {
            switch (c) {
                case '(':
                    openParentheses++;
                    break;
                case ')':
                    openParentheses--;
                    break;
                case '{':
                    openCurly++;
                    break;
                case '}':
                    openCurly--;
                    break;
                case '[':
                    openSquare++;
                    break;
                case ']':
                    openSquare--;
                    break;
                default:
                    break;
            }

            if (openParentheses < 0 || openCurly < 0 || openSquare < 0) {
                result = false;
                break;
            }
        }

        if (openParentheses > 0 || openCurly > 0 || openSquare > 0) {
            result = false;
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(validate("(kjds(hfkj)sdhf"));
        System.out.println(validate("a(bcd)d"));
        System.out.println(validate("(sfdsf)(fsfsf"));
        System.out.println(validate("{[]}()"));
        System.out.println(validate("{[}]"));
    }
}