{"id":8068,"date":"2021-02-06T08:30:29","date_gmt":"2021-02-06T16:30:29","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8068"},"modified":"2021-02-06T08:30:56","modified_gmt":"2021-02-06T16:30:56","slug":"leetcode-1750-minimum-length-of-string-after-deleting-similar-ends","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1750-minimum-length-of-string-after-deleting-similar-ends\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1750. Minimum Length of String After Deleting Similar Ends"},"content":{"rendered":"\n

Given a string s<\/code> consisting only of characters 'a'<\/code>, 'b'<\/code>, and 'c'<\/code>. You are asked to apply the following algorithm on the string any number of times:<\/p>\n\n\n\n

  1. Pick a non-empty<\/strong> prefix from the string s<\/code> where all the characters in the prefix are equal.<\/li>
  2. Pick a non-empty<\/strong> suffix from the string s<\/code> where all the characters in this suffix are equal.<\/li>
  3. The prefix and the suffix should not intersect at any index.<\/li>
  4. The characters from the prefix and suffix must be the same.<\/li>
  5. Delete both the prefix and the suffix.<\/li><\/ol>\n\n\n\n

    Return the minimum length<\/strong> of <\/em>s<\/code> after performing the above operation any number of times (possibly zero times)<\/em>.<\/p>\n\n\n\n

    Example 1:<\/strong><\/p>\n\n\n\n

    Input:<\/strong> s = \"ca\"\nOutput:<\/strong> 2\nExplanation: <\/strong>You can't remove any characters, so the string stays as is.\n<\/pre>\n\n\n\n
    Example 2:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> s = \"cabaabac\"\nOutput:<\/strong> 0\nExplanation:<\/strong> An optimal sequence of operations is:\n- Take prefix = \"c\" and suffix = \"c\" and remove them, s = \"abaaba\".\n- Take prefix = \"a\" and suffix = \"a\" and remove them, s = \"baab\".\n- Take prefix = \"b\" and suffix = \"b\" and remove them, s = \"aa\".\n- Take prefix = \"a\" and suffix = \"a\" and remove them, s = \"\".<\/pre>\n\n\n\n
    Example 3:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> s = \"aabccabba\"\nOutput:<\/strong> 3\nExplanation:<\/strong> An optimal sequence of operations is:\n- Take prefix = \"aa\" and suffix = \"a\" and remove them, s = \"bccabb\".\n- Take prefix = \"b\" and suffix = \"bb\" and remove them, s = \"cca\".\n<\/pre>\n\n\n\n
    Constraints:<\/strong><\/p>\n\n\n\n
    • 1 <= s.length <= 105<\/sup><\/code><\/li>
    • s<\/code> only consists of characters 'a'<\/code>, 'b'<\/code>, and 'c'<\/code>.<\/li><\/ul>\n\n\n\n
      Solution: Two Pointers + Greedy<\/strong><\/h2>\n\n\n\n
      Delete all the chars for each prefix and suffix pair. <\/p>\n\n\n\n
      Time complexity: O(n)
      Space complexity: O(1)<\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minimumLength(string s) {\n    int l = 0, r = s.length() - 1;\n    while (l < r) {\n      if (s[l] != s[r]) break;\n      const char c = s[l];\n      while (l <= r && s[l] == c) ++l;\n      while (l <= r && s[r] == c) --r;\n    }\n    return r - l + 1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      Given a string s consisting only of characters ‘a’, ‘b’, and ‘c’. You are asked to apply the following algorithm on the string any number of times: Pick a non-empty prefix from…<\/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,4],"class_list":["post-8068","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-medium","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8068","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=8068"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8068\/revisions"}],"predecessor-version":[{"id":8070,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8068\/revisions\/8070"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8068"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8068"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8068"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}