{"id":7947,"date":"2021-01-09T19:12:39","date_gmt":"2021-01-10T03:12:39","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7947"},"modified":"2021-01-09T19:50:57","modified_gmt":"2021-01-10T03:50:57","slug":"leetcode-1717-maximum-score-from-removing-substrings","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1717-maximum-score-from-removing-substrings\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1717. Maximum Score From Removing Substrings"},"content":{"rendered":"\n<p>You are given a string&nbsp;<code>s<\/code>&nbsp;and two integers&nbsp;<code>x<\/code>&nbsp;and&nbsp;<code>y<\/code>. You can perform two types of operations any number of times.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Remove substring&nbsp;<code>\"ab\"<\/code>&nbsp;and gain&nbsp;<code>x<\/code>&nbsp;points.<ul><li>For example, when removing&nbsp;<code>\"ab\"<\/code>&nbsp;from&nbsp;<code>\"c<u>ab<\/u>xbae\"<\/code>&nbsp;it becomes&nbsp;<code>\"cxbae\"<\/code>.<\/li><\/ul><\/li><li>Remove substring&nbsp;<code>\"ba\"<\/code>&nbsp;and gain&nbsp;<code>y<\/code>&nbsp;points.<ul><li>For example, when removing&nbsp;<code>\"ba\"<\/code>&nbsp;from&nbsp;<code>\"cabx<u>ba<\/u>e\"<\/code>&nbsp;it becomes&nbsp;<code>\"cabxe\"<\/code>.<\/li><\/ul><\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the maximum points you can gain after applying the above operations on<\/em>&nbsp;<code>s<\/code>.<\/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 = \"cdbcbbaaabab\", x = 4, y = 5\n<strong>Output:<\/strong> 19\n<strong>Explanation:<\/strong>\n- Remove the \"ba\" underlined in \"cdbcbbaaabab\". Now, s = \"cdbcbbaaab\" and 5 points are added to the score.\n- Remove the \"ab\" underlined in \"cdbcbbaaab\". Now, s = \"cdbcbbaa\" and 4 points are added to the score.\n- Remove the \"ba\" underlined in \"cdbcbbaa\". Now, s = \"cdbcba\" and 5 points are added to the score.\n- Remove the \"ba\" underlined in \"cdbcba\". Now, s = \"cdbc\" and 5 points are added to the score.\nTotal score = 5 + 4 + 5 + 5 = 19.<\/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 = \"aabbaaxybbaabb\", x = 5, y = 4\n<strong>Output:<\/strong> 20\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<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= x, y &lt;= 10<sup>4<\/sup><\/code><\/li><li><code>s<\/code>&nbsp;consists of lowercase English letters.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy + Stack<\/strong><\/h2>\n\n\n\n<p>Remove the pattern with the larger score first.<\/p>\n\n\n\n<p>Using a stack to remove all occurrences of a pattern in place in O(n) Time.<\/p>\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++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maximumGain(string s, int x, int y) {\n    \/\/ Remove patttern p from s for t points each.\n    \/\/ Returns the total score.\n    auto remove = [&](const string& p, int t) {\n      int total = 0;\n      int i = 0;\n      for (int j = 0; j < s.size(); ++j, ++i) {\n        s[i] = s[j];\n        if (i &#038;&#038; s[i - 1] == p[0] &#038;&#038; s[i] == p[1]) {\n          i -= 2;\n          total += t;\n        }\n      }\n      s.resize(i); \n      return total;\n    };\n    string px{\"ab\"};\n    string py{\"ba\"};\n    if (y > x) {\n      swap(px, py);\n      swap(x, y);\n    }    \n    return remove(px, x) + remove(py, y);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a string&nbsp;s&nbsp;and two integers&nbsp;x&nbsp;and&nbsp;y. You can perform two types of operations any number of times. Remove substring&nbsp;&#8220;ab&#8221;&nbsp;and gain&nbsp;x&nbsp;points. For example, when removing&nbsp;&#8220;ab&#8221;&nbsp;from&nbsp;&#8220;cabxbae&#8221;&nbsp;it&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,177,686,180,4],"class_list":["post-7947","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-medium","tag-removal","tag-stack","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7947","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=7947"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7947\/revisions"}],"predecessor-version":[{"id":7949,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7947\/revisions\/7949"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7947"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7947"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7947"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}