Skip to content

1737. Change Minimum Characters to Satisfy One of Three Conditions

Difficulty Topics

Description

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 a is strictly less than every letter in b in the alphabet.
  • Every letter in b is strictly less than every letter in a in the alphabet.
  • Both a and b consist 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 <= 105
  • a and b consist only of lowercase letters.

Solution

change-minimum-characters-to-satisfy-one-of-three-conditions.py
class Solution:
    def minCharacters(self, A: str, B: str) -> int:
        countA = Counter(ord(c) - ord('a') for c in A)
        countB = Counter(ord(c) - ord('a') for c in B)

        def operation1(a, b):
            # a < i, b >= i
            res = float('inf')
            for i in range(1,26):
                count = sum(a[j] for j in range(i))
                count += sum(b[j] for j in range(i, 26))

                res = min(res, count)

            return res

        def operation3(a, b):
            res = float('-inf')

            for i in range(26):
                res = max(res, a[i] + b[i])

            return len(A) + len(B) - res

        return min(operation1(countA, countB), operation1(countB, countA), operation3(countA, countB))