title
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
class Solution:
def minCharacters(self, a: str, b: str) -> int:
la, lb = len(a), len(b)
countA = defaultdict(int)
countB = defaultdict(int)
for i in a:
countA[ord(i)] += 1
for i in b:
countB[ord(i)] += 1
ans = float('inf')
a1sum, b1sum = 0, 0
for t in range(ord('a'), ord('z')):
a1sum += countA[t]
b1sum += countB[t]
ans = min(ans, la - a1sum + b1sum, lb - b1sum + a1sum, la + lb - countA[t] - countB[t])
# z的情况
ans = min(ans, la+lb-countA[ord('z')] - countB[ord('z')])
return ans