{"id":7225,"date":"2020-08-10T00:51:16","date_gmt":"2020-08-10T07:51:16","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7225"},"modified":"2020-08-10T00:56:20","modified_gmt":"2020-08-10T07:56:20","slug":"leetcode-1544-make-the-string-great","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/stack\/leetcode-1544-make-the-string-great\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1544. Make The String Great"},"content":{"rendered":"\n<p>Given a string&nbsp;<code>s<\/code>&nbsp;of lower and upper case English letters.<\/p>\n\n\n\n<p>A good string is a string which doesn&#8217;t have&nbsp;<strong>two adjacent characters<\/strong>&nbsp;<code>s[i]<\/code>&nbsp;and&nbsp;<code>s[i + 1]<\/code>&nbsp;where:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>0 &lt;= i &lt;= s.length - 2<\/code><\/li><li><code>s[i]<\/code>&nbsp;is a lower-case letter and&nbsp;<code>s[i + 1]<\/code>&nbsp;is the same letter but in upper-case&nbsp;or&nbsp;<strong>vice-versa<\/strong>.<\/li><\/ul>\n\n\n\n<p>To make the string good, you can choose&nbsp;<strong>two adjacent<\/strong>&nbsp;characters that make the string bad and remove them. You can keep doing this until the string becomes good.<\/p>\n\n\n\n<p>Return&nbsp;<em>the string<\/em>&nbsp;after making it good. The answer is guaranteed to be unique under the given constraints.<\/p>\n\n\n\n<p><strong>Notice<\/strong>&nbsp;that an empty string is also good.<\/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 = \"leEeetcode\"\n<strong>Output:<\/strong> \"leetcode\"\n<strong>Explanation:<\/strong> In the first step, either you choose i = 1 or i = 2, both will result \"leEeetcode\" to be reduced to \"leetcode\".\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 = \"abBAcC\"\n<strong>Output:<\/strong> \"\"\n<strong>Explanation:<\/strong> We have many possible scenarios, and all lead to the same answer. For example:\n\"abBAcC\" --&gt; \"aAcC\" --&gt; \"cC\" --&gt; \"\"\n\"abBAcC\" --&gt; \"abBA\" --&gt; \"aA\" --&gt; \"\"\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 = \"s\"\n<strong>Output:<\/strong> \"s\"\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;= 100<\/code><\/li><li><code>s<\/code>&nbsp;contains only lower and upper case English letters.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Stack<\/strong><\/h2>\n\n\n\n<p>Iterator over the string, compare current char with top of the stack, if they are a bad pair, pop the stack (remove both of them). Otherwise, push the current char onto the stack.<\/p>\n\n\n\n<p>input: &#8220;abBAcC&#8221;<br>&#8220;a&#8221;<br>&#8220;ab&#8221;<br>&#8220;a<s>bB<\/s>&#8221; -> &#8220;a&#8221;<br>&#8220;<s>aA<\/s>&#8221; -> &#8220;&#8221;<br>&#8220;c&#8221;<br>&#8220;<s>cC<\/s>&#8221; -> &#8220;&#8221;<br>ans = &#8220;&#8221;<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/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  string makeGood(string s) {\n    string ans;\n    for (char c : s) {      \n      if (ans.length() && \n          abs(ans.back() - c) == abs('a' - 'A'))\n        ans.pop_back();        \n      else\n        ans.push_back(c);\n    }\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"java\">\nclass Solution {\n  public String makeGood(String s) {\n    var sb = new StringBuilder();\n    for (int i = 0; i < s.length(); ++i) {\n      int l = sb.length();\n      if (l > 0 && Math.abs(sb.charAt(l - 1) - s.charAt(i)) == 32) {\n        sb.setLength(l - 1); \/\/ remove last char\n      } else {\n        sb.append(s.charAt(i));\n      }\n    }\n    return sb.toString();\n  }\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\nclass Solution:\n  def makeGood(self, s: str) -> str:\n    ans = []\n    for c in s:\n      if ans and abs(ord(ans[-1]) - ord(c)) == 32:\n        ans.pop()\n      else:\n        ans.append(c)\n    return \"\".join(ans)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a string&nbsp;s&nbsp;of lower and upper case English letters. A good string is a string which doesn&#8217;t have&nbsp;two adjacent characters&nbsp;s[i]&nbsp;and&nbsp;s[i + 1]&nbsp;where: 0 &lt;= i&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[407],"tags":[222,180,4],"class_list":["post-7225","post","type-post","status-publish","format-standard","hentry","category-stack","tag-easy","tag-stack","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7225","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=7225"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7225\/revisions"}],"predecessor-version":[{"id":7228,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7225\/revisions\/7228"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7225"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7225"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7225"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}