Last Updated: 7 Jan, 2021
Minimum Parentheses
Easy
Asked in companies
Given a string "pattern", which contains only two types of characters ‘(’, ‘)’.
Your task is to find the minimum number of parentheses either ‘(’, ‘)’ we must add the parentheses in string ‘pattern’ and the resulted string is valid.
Condition for valid string-
Every opening parenthesis ‘(’ must have a correct closing parenthesis ‘)’.
Example - ‘(()(()))’, ‘()()()’, ‘((()))’ are valid string, and ‘(((’, ‘(()’, ‘)(())’ are invalid string.
Note:
1. You are not required to print the output explicitly, it has already been taken care of. Just implement the function and return the minimum number of parentheses required to make a string valid.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.
The first line of each test case contains a string "pattern".
Output Format:
For each test case, return the minimum number of parentheses.
Constraints:
1 <= T <= 50
1 <= N <= 10^4
Where ‘T’ is the total number of test cases, ‘N’ denotes the length of string "pattern".
Time limit: 1 second
Approaches
The basic idea is that, store the count of ‘(‘ and ‘)’ and try to balance ‘(‘ and ‘)’.
- Use two variables “openBr” = 0 and “closeBr” = 0, where “openBr” store the count of opening parentheses ‘(’ and “closeBr” store count of closing parentheses ‘)’. And a “count” = 0 to store the minimum number of parentheses required to make string “pattern” valid.
- Iterate a loop ‘i’ for every character of “pattern”.
- If character at ‘i’ is ‘(‘ then increase “openBr” = “openBr”+1 else increase “closeBr” = “closeBr” + 1.
- If any point of the stage, “closeBr” > “openBr”
- Then we need extra “closeBr” - “openBr” parentheses which are not balanced add “count” = “count” + “closeBr” - “openBr”.
- Update “closeBr” = 0 and “openBr” = 0.
- The above step is ensuring that we don’t have extra closing parentheses ‘)’.
- After all iteration we need to balance only opening parentheses, so add “count” = “openBr” - “closeBr”.
- Return “count”.