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