Problem Statement

Given an string or expression which only consists of characters like (, ), [, ], {, } . Validate if the string has balanced parentheses.
A string has balanced parentheses, if every open bracket has an associated closed one and they exist in the right order.

Solution Explanation

As the problem statement explains, a string is valid if it has balanced parentheses, for example,
()[]{} is valid and (()[] is not, because the second string doesn't have a closing ).

Based on the above example, we can make a simple inference that number of opening and closing brackets have to be same for a string is balanced. While this is a necessary condition, this is not sufficient. Consider the below example,
([)] this string is not valid because of the order.

For the order to be valid, the last opening bracket should have a matching closed one. So we could follow the below kind of algorithm.

Psuedo Code for Valid parentheses

• Parse the string and read one character at a time.
• If the character is an opening bracket, put it in a bucket
• If the character is a closed one, find if it's matching opening bracket is at the top of the bucket, if it is, remove it from the bucket.
• At the end of the parsing it, if the bucket is not empty, then the string doesn't have balanced parentheses or valid parentheses.

To convert this to Java code, we could Stack data-structure in place of the bucket since it provides us the same functionality and we could store the mapping of open to closed brackets in hashmap which allows us to compare if a bracket in the bucket is the matching one.

Below is the Java implementation for balanced parentheses,

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        Stack<Character> stack = new Stack<>();
        for(char c : s.toCharArray()){
            if(map.containsKey(c)){
                stack.push(c);
            } else if(!stack.empty() && map.get(stack.peek())==c){
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.empty();
    }
}

####### Time Complexity for balanced parentheses
We only read the string once, so the time complexity is O(n), but we use a map and stack for storage, so space complexity O(size_of_string).