Change Minimum Characters to Satisfy One of Three Conditions

Intuition

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.

Solution


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