You are given two strings a and b that consist of lowercase letters. In one operation, you can change any character in a or b to any lowercase letter.
Your goal is to satisfy one of the following three conditions:
- Every letter in
ais strictly less than every letter inbin the alphabet. - Every letter in
bis strictly less than every letter inain the alphabet. - Both
aandbconsist of only one distinct letter.
Return the minimum number of operations needed to achieve your goal.
Example 1:
Input: a = "aba", b = "caa" Output: 2 Explanation: Consider the best way to make each condition true: 1) Change b to "ccc" in 2 operations, then every letter in a is less than every letter in b. 2) Change a to "bbb" and b to "aaa" in 3 operations, then every letter in b is less than every letter in a. 3) Change a to "aaa" and b to "aaa" in 2 operations, then a and b consist of one distinct letter. The best way was done in 2 operations (either condition 1 or condition 3).
Example 2:
Input: a = "dabadd", b = "cda" Output: 3 Explanation: The best way is to make condition 1 true by changing b to "eee".
Constraints:
1 <= a.length, b.length <= 105aandbconsist only of lowercase letters.
Solution: Brute Force
Time complexity: O(26*(m+n))
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: int minCharacters(string a, string b) { auto change = [](const string& a, const string& b) { int ans = INT_MAX; for (char c = 'a'; c < 'z'; ++c) { int ops = 0; for (char x : a) ops += x > c; for (char x : b) ops += x <= c; ans = min(ans, ops); } return ans; }; int ans = min(change(a, b), change(b, a)); for (char c = 'a'; c <= 'z'; ++c) { int ops = a.size() - count(begin(a), end(a), c) + b.size() - count(begin(b), end(b), c); ans = min(ans, ops); } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment