Minimum Add to Make Parentheses Valid

Google Interview Question

Problem Overview

Difficulty: Medium
LeetCode Pattern: Stack

You are given a string s containing only ( and ). In one move, you can insert a parenthesis anywhere. Return the minimum number of insertions needed to make s valid.

Note: A string of parentheses is valid if:

• It is empty.

• Or it can be formed by:

  • concatenating two valid strings.

• Or it is wrapped like:

  • (A…