{"id":7219,"date":"2020-08-09T10:15:43","date_gmt":"2020-08-09T17:15:43","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7219"},"modified":"2020-08-09T10:17:58","modified_gmt":"2020-08-09T17:17:58","slug":"leetcode-1541-minimum-insertions-to-balance-a-parentheses-string","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1541-minimum-insertions-to-balance-a-parentheses-string\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1541. Minimum Insertions to Balance a Parentheses String"},"content":{"rendered":"\n<p>Given a parentheses string&nbsp;<code>s<\/code>&nbsp;containing only the characters&nbsp;<code>'('<\/code>&nbsp;and&nbsp;<code>')'<\/code>. A parentheses string is&nbsp;<strong>balanced<\/strong>&nbsp;if:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Any left parenthesis&nbsp;<code>'('<\/code>&nbsp;must have a corresponding two consecutive right parenthesis&nbsp;<code>'))'<\/code>.<\/li><li>Left parenthesis&nbsp;<code>'('<\/code>&nbsp;must go before the corresponding two&nbsp;consecutive right parenthesis&nbsp;<code>'))'<\/code>.<\/li><\/ul>\n\n\n\n<p>For example,&nbsp;<code>\"())\"<\/code>,&nbsp;<code>\"())(())))\"<\/code>&nbsp;and&nbsp;<code>\"(())())))\"<\/code>&nbsp;are&nbsp;balanced,&nbsp;<code>\")()\"<\/code>,&nbsp;<code>\"()))\"<\/code>&nbsp;and&nbsp;<code>\"(()))\"<\/code>&nbsp;are not balanced.<\/p>\n\n\n\n<p>You can insert the characters &#8216;(&#8216; and &#8216;)&#8217; at any position of the string to balance it if needed.<\/p>\n\n\n\n<p>Return&nbsp;<em>the minimum number of insertions<\/em>&nbsp;needed to make&nbsp;<code>s<\/code>&nbsp;balanced.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"(()))\"\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> The second '(' has two matching '))', but the first '(' has only ')' matching. We need to to add one more ')' at the end of the string to be \"(())))\" which is balanced.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"())\"\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> The string is already balanced.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"))())(\"\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> Add '(' to match the first '))', Add '))' to match the last '('.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"((((((\"\n<strong>Output:<\/strong> 12\n<strong>Explanation:<\/strong> Add 12 ')' to balance the string.\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \")))))))\"\n<strong>Output:<\/strong> 5\n<strong>Explanation:<\/strong> Add 4 '(' at the beginning of the string and one ')' at the end. The string becomes \"(((())))))))\".\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= s.length &lt;= 10^5<\/code><\/li><li><code>s<\/code>&nbsp;consists of&nbsp;<code>'('<\/code>&nbsp;and&nbsp;<code>')'<\/code>&nbsp;only.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Counting<\/strong><\/h2>\n\n\n\n<p>Count how many close parentheses we need.<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>if s[i] is &#8216;)&#8217;, we decrease the counter.<ol><li>if counter becomes negative, means we need to insert &#8216;(&#8216;<ol><li>increase ans by 1, increase the counter by 2, we need one more &#8216;)&#8217;<\/li><li>&#8216;)&#8217; -> &#8216;()&#8217; <\/li><\/ol><\/li><\/ol><\/li><li>if s[i] is &#8216;(&#8216;<ol><li>if we have an odd counter, means there is a unbalanced &#8216;)&#8217; e.g. &#8216;(()(&#8216;, counter is 3<ol><li>need to insert &#8216;)&#8217;, decrease counter, increase ans<\/li><li>&#8216;(()(&#8216; -> &#8216;(<s>())<\/s>(&#8216;, counter = 2<\/li><\/ol><\/li><li>increase counter by 2, each &#8216;(&#8216; needs two &#8216;)&#8217;s. &#8216;(<s>())<\/s>(&#8216; -> counter = 4<\/li><\/ol><\/li><li>Once done, if counter is greater than zero, we need insert that much &#8216;)s&#8217;<ol><li>counter = 5, &#8216;((()&#8217; -> &#8216;((())))))&#8217;<\/li><\/ol><\/li><\/ol>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int minInsertions(string s) {\n    int ans = 0;\n    int close = 0; \/\/ # of ')' needed.    \n    for (char c : s) {\n      if (c == ')') {\n        if (--close < 0) {          \n          \/\/ need to insert one '('\n          \/\/ ')' -> '()'\n          ++ans;\n          close += 2;\n        }\n      } else {\n        if (close & 1) {          \n          \/\/ need to insert one ')'\n          \/\/ case '(()(' -> '(())('\n          --close;\n          ++ans;\n        }\n        close += 2; \/\/ need two ')'s\n      }\n    }\n    return ans + close;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a parentheses string&nbsp;s&nbsp;containing only the characters&nbsp;&#8216;(&#8216;&nbsp;and&nbsp;&#8216;)&#8217;. A parentheses string is&nbsp;balanced&nbsp;if: Any left parenthesis&nbsp;&#8216;(&#8216;&nbsp;must have a corresponding two consecutive right parenthesis&nbsp;&#8216;))&#8217;. Left parenthesis&nbsp;&#8216;(&#8216;&nbsp;must go before&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[8,177,421,4],"class_list":["post-7219","post","type-post","status-publish","format-standard","hentry","category-string","tag-counting","tag-medium","tag-parentheses","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7219","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7219"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7219\/revisions"}],"predecessor-version":[{"id":7221,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7219\/revisions\/7221"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7219"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7219"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7219"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}