In this contribution, I solved the problem of Minimum Add to Make Parentheses Valid.
Problem statement:
A parentheses string is valid if and only if:
It is the empty string,
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.
You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.
Return the minimum number of moves required to make s valid.
Fixes:
My code beats 100% in time complexity.
Type of Change
[x] Question Added
[x] Solution Added
[ ] Other (please specify):
How to Test
Run the code for the different test cases
Checklist
[x] I have performed a self-review of my code.
[x] I have commented my code, particularly in hard-to-understand areas.
[ ] I have made corresponding changes to the documentation (if applicable).
[x] My changes generate no new warnings.
[ ] I have added tests to cover my changes (if applicable).
[x] All new and existing tests pass.
Additional Notes
Alternative solution to the problem is using a stack which increases the space complexity to O(n) . When we encounter an open bracket, we push it onto the stack. When we encounter a close bracket we pop the open if the stack is not empty. But if its empty we increment our moves. In the end after iterating though the string if some open brackets still remain on the stack we add that count to moves. That gives our final answer
Description
In this contribution, I solved the problem of Minimum Add to Make Parentheses Valid.
Problem statement: A parentheses string is valid if and only if: It is the empty string, It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string. You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. Return the minimum number of moves required to make s valid.
Fixes:
My code beats 100% in time complexity.
Type of Change
How to Test
Run the code for the different test cases
Checklist
Additional Notes
Alternative solution to the problem is using a stack which increases the space complexity to O(n) . When we encounter an open bracket, we push it onto the stack. When we encounter a close bracket we pop the open if the stack is not empty. But if its empty we increment our moves. In the end after iterating though the string if some open brackets still remain on the stack we add that count to moves. That gives our final answer