/** Runtime: 1 ms, faster than 46.42% of Java online submissions for Minimum Add to Make Parentheses Valid.
Memory Usage: 34.5 MB, less than 100.00% of Java online submissions for Minimum Add to Make Parentheses Valid.**/
class Solution {
    public int minAddToMakeValid(String S) {
        char[] arr = S.toCharArray();
        Queue<Character> queue = new LinkedList<>();

        int count = 0;

        for(char c : arr) {
            if(c == '(') {
                queue.add(c);
            }

            if(c == ')') {
               if(queue.isEmpty()) {
                   count++;
               } else {
                   queue.poll();
               }
            }
        }

        return count + queue.size();
    }
}