Solve 3 sub-problems one by one and then return the minumum one.
We try to make a to be strictly less than b. In this case, we need to choose a character c from a to y and make a to be less than or equal to c, and b to be greater than c.
Note that we can't use z because there is no way to make characters in b to be strictly greater than z.
The same as 1..
Find the most frequent character in both a and b, then change all other characters to it.
import string
class Solution:
def minCharacters(self, a: str, b: str) -> int:
a_less_than_b = self._less_than(a, b)
b_less_than_a = self._less_than(b, a)
min_change = len(a) + len(b)
for c in string.ascii_lowercase:
min_change = min(
min_change,
len(a) + len(b) - a.count(c) - b.count(c)
)
return min([a_less_than_b, b_less_than_a, min_change])
def _less_than(self, a, b):
min_change = len(a) + len(b)
for c in string.ascii_lowercase[:-1]:
tmp = 0
for c1 in a:
if c1 > c:
tmp += 1
for c1 in b:
if c1 <= c:
tmp += 1
min_change = min(min_change, tmp)
return min_change