Matching parenthesis | Google Interview Question & Solution
Here's your coding interview problem for today. This problem was asked by Google.
Given a string of parentheses, write a function to compute the minimum number of parentheses to be removed to make the string valid (i.e. each open parenthesis is eventually closed).
For example, given the string "()())()", you should return 1. Given the string ")(", you should return 2, since we must remove all of them.
Idea behind the solution
The solution was inspired by the Shunting yard algorithm from Edsger Dijkstra. This algorithm is used for solving mathematical expressions to produce a Polish Notation from the given conventional notation. It deals perfectly with matching parenthesis.
We basically need to stack every
( and pop the top of the stack for every
). If the stack is empty while trying to pop the top of it, then there is a
) not being openend by an
(. If there is any
( in the stack, them we have
( not being closed by any
). The result is the sum of the size of the stack and how many times we failed to pop the top of the stack because it was empty.
Please check the Solution.java snippet for the solution.
This solution originally posted at: Github by @Murillo2380