python simple beats 100% (as of 22nd October, 2018)
The idea is to keep a separate counter for invalid left and right parenthesis. Whenever a new left parenthesis is encountered, the left counter is incremented b
The idea is to keep a separate counter for invalid left and right parenthesis. Whenever a new left parenthesis is encountered, the left counter is incremented by 1 (assuming it to be an invalid parenthesis). When a right parenthesis is encountered, the left counter is decremented by 1 (since we found a pair, we have one less invalid left parenthesis).  But there is a catch, it may happen that we encounter a right parenthesis while the count of left count is 0, in which case we'll increment the right counter by 1 (because this is an invalid right parenthesis)

```
        left = 0
        right = 0
        
        for p in S:
            if p == "(":
                left += 1
            elif p == ")" and left <= 0:
                right += 1
            else:
                left -= 1
        
        return left + right
```
[]