1737. Change Minimum Characters to Satisfy One of Three Conditions

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.

 

Solutions

Solution: Prefix Sum

• Time complexity: O(m+n)
• Space complexity: O(26)

 

JavaScript

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
const minCharacters = function (a, b) {
  const CODE_BASE = 'a'.charCodeAt(0);
  const m = a.length;
  const n = b.length;
  const countA = Array.from({length: 26}).fill(0);
  const countB = Array.from({length: 26}).fill(0);
  let result = m + n;

  for (const char of a) countA[char.charCodeAt(0) - CODE_BASE] += 1;
  for (const char of b) countB[char.charCodeAt(0) - CODE_BASE] += 1;
  for (let index = 0; index < 26; index++) {
    result = Math.min(m + n - countA[index] - countB[index], result);

    if (index > 0) {
      countA[index] += countA[index - 1];
      countB[index] += countB[index - 1];
    }
    if (index >= 25) continue;
    result = Math.min(m - countA[index] + countB[index], result);
    result = Math.min(n + countA[index] - countB[index], result);
  }
  return result;
};