Skip to content

Latest commit

 

History

History
69 lines (52 loc) · 2.28 KB

README.md

File metadata and controls

69 lines (52 loc) · 2.28 KB

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.

  • For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))".

Return the minimum number of moves required to make s valid.

 

Example 1:

Input: s = "())"
Output: 1

Example 2:

Input: s = "((("
Output: 3

 

Constraints:

  • 1 <= s.length <= 1000
  • s[i] is either '(' or ')'.

Companies:
Facebook, Twitter, Amazon, Visa

Related Topics:
String, Stack, Greedy

Similar Questions:

Solution 1.

// OJ: https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minAddToMakeValid(string s) {
        int left = 0, invalidRight = 0;
        for (char c : s) {
            if (c == '(') ++left;
            else if (left) --left;
            else ++invalidRight;
        }
        return invalidRight + left;
    }
};