README_EN.md

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

Prefix Sum

Python3

Java

TypeScript

function minCharacters(a: string, b: string): number {
    const m = a.length, n = b.length;
    let count1 = new Array(26).fill(0);
    let count2 = new Array(26).fill(0);
    const base = 'a'.charCodeAt(0);

    for (let char of a) {
        count1[char.charCodeAt(0) - base]++;
    }
    for (let char of b) {
        count2[char.charCodeAt(0) - base]++;
    }
    
    let pre1 = 0, pre2 = 0;
    let ans = m + n;
    for (let i = 0; i < 25; i++) {
        pre1 += count1[i];
        pre2 += count2[i];
        // case1， case2， case3
        ans = Math.min(ans, m - pre1 + pre2, pre1 + n - pre2, m + n - count1[i] - count2[i]);
    }
    ans = Math.min(ans, m + n - count1[25] - count2[25]);
    
    return ans;
};

...