{"id":8025,"date":"2021-01-23T21:58:04","date_gmt":"2021-01-24T05:58:04","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8025"},"modified":"2021-01-23T21:59:42","modified_gmt":"2021-01-24T05:59:42","slug":"leetcode-1737-change-minimum-characters-to-satisfy-one-of-three-conditions","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1737-change-minimum-characters-to-satisfy-one-of-three-conditions\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions"},"content":{"rendered":"\n<p>You are given two strings&nbsp;<code>a<\/code>&nbsp;and&nbsp;<code>b<\/code>&nbsp;that consist of lowercase letters. In one operation, you can change any character in&nbsp;<code>a<\/code>&nbsp;or&nbsp;<code>b<\/code>&nbsp;to&nbsp;<strong>any lowercase letter<\/strong>.<\/p>\n\n\n\n<p>Your goal is to satisfy&nbsp;<strong>one<\/strong>&nbsp;of the following three conditions:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>Every<\/strong>&nbsp;letter in&nbsp;<code>a<\/code>&nbsp;is&nbsp;<strong>strictly less<\/strong>&nbsp;than&nbsp;<strong>every<\/strong>&nbsp;letter in&nbsp;<code>b<\/code>&nbsp;in the alphabet.<\/li><li><strong>Every<\/strong>&nbsp;letter in&nbsp;<code>b<\/code>&nbsp;is&nbsp;<strong>strictly less<\/strong>&nbsp;than&nbsp;<strong>every<\/strong>&nbsp;letter in&nbsp;<code>a<\/code>&nbsp;in the alphabet.<\/li><li><strong>Both<\/strong>&nbsp;<code>a<\/code>&nbsp;and&nbsp;<code>b<\/code>&nbsp;consist of&nbsp;<strong>only one<\/strong>&nbsp;distinct letter.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>minimum<\/strong>&nbsp;number of operations needed to achieve your goal.<\/em><\/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> a = \"aba\", b = \"caa\"\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> Consider the best way to make each condition true:\n1) Change b to \"ccc\" in 2 operations, then every letter in a is less than every letter in b.\n2) Change a to \"bbb\" and b to \"aaa\" in 3 operations, then every letter in b is less than every letter in a.\n3) Change a to \"aaa\" and b to \"aaa\" in 2 operations, then a and b consist of one distinct letter.\nThe best way was done in 2 operations (either condition 1 or condition 3).\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> a = \"dabadd\", b = \"cda\"\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> The best way is to make condition 1 true by changing b to \"eee\".\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= a.length, b.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>a<\/code>&nbsp;and&nbsp;<code>b<\/code>&nbsp;consist only of lowercase letters.<\/li><\/ul>\n\n\n\n<p><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Brute Force<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(26*(m+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 minCharacters(string a, string b) {\n    auto change = [](const string& a, const string& b) {\n      int ans = INT_MAX; \n      for (char c = 'a'; c < 'z'; ++c) { \n        int ops = 0;\n        for (char x : a) ops += x > c; \n        for (char x : b) ops += x <= c; \n        ans = min(ans, ops);\n      }\n      return ans;\n    };        \n    int ans = min(change(a, b), change(b, a));\n    for (char c = 'a'; c <= 'z'; ++c) {\n      int ops = a.size() - count(begin(a), end(a), c) + \n         b.size() - count(begin(b), end(b), c);              \n      ans = min(ans, ops);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given two strings&nbsp;a&nbsp;and&nbsp;b&nbsp;that consist of lowercase letters. In one operation, you can change any character in&nbsp;a&nbsp;or&nbsp;b&nbsp;to&nbsp;any lowercase letter. Your goal is to satisfy&nbsp;one&nbsp;of&#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":[254,4],"class_list":["post-8025","post","type-post","status-publish","format-standard","hentry","category-string","tag-counter","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8025","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=8025"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8025\/revisions"}],"predecessor-version":[{"id":8027,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8025\/revisions\/8027"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8025"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8025"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8025"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}