Formatted question description: https://leetcode.ca/all/1737.html

# 1737. Change Minimum Characters to Satisfy One of Three Conditions

Medium

## 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 <= 10^5
• a and b consist only of lowercase letters.

## Solution

For the first two conditions, calculate the number of occurrences of each letter in each of the strings a and b respectively, and calculate the prefix sums and the suffix sums respectively. Then loop over the number of occurrences. For each i from 0 to 24, calculate the number of operations to change letters in a to letters in indices 0 to i and change letters in b to letters in indices i + 1 to 25, and calculate the number of operations to change letters in b to letters in indices 0 to i and change letters in a to letters in indices i + 1 to 25. Maintain the minimum number of operations during the process, which is the minimum number of operations for conditions 1 and 2.

For condition 3, obtain the maximum occurrence of letters in a and b respectively, and the remaining letters need to be changed to such a letter for each string.

Finally, return the minimum number of operations among three conditions.

class Solution {
public int minCharacters(String a, String b) {
int[] aCounts = new int[26];
int[] bCounts = new int[26];
int aMaxCount = 0, bMaxCount = 0;
int aLength = a.length(), bLength = b.length();
for (int i = 0; i < aLength; i++) {
char c = a.charAt(i);
aCounts[c - 'a']++;
aMaxCount = Math.max(aMaxCount, aCounts[c - 'a']);
}
for (int i = 0; i < bLength; i++) {
char c = b.charAt(i);
bCounts[c - 'a']++;
bMaxCount = Math.max(bMaxCount, bCounts[c - 'a']);
}
int[] aCountsPrefix = new int[26];
int[] aCountsSuffix = new int[26];
int[] bCountsPrefix = new int[26];
int[] bCountsSuffix = new int[26];
aCountsPrefix[0] = aCounts[0];
bCountsPrefix[0] = bCounts[0];
for (int i = 1; i < 26; i++) {
aCountsPrefix[i] = aCountsPrefix[i - 1] + aCounts[i];
bCountsPrefix[i] = bCountsPrefix[i - 1] + bCounts[i];
}
aCountsSuffix[25] = aCounts[25];
bCountsSuffix[25] = bCounts[25];
for (int i = 24; i >= 0; i--) {
aCountsSuffix[i] = aCountsSuffix[i + 1] + aCounts[i];
bCountsSuffix[i] = bCountsSuffix[i + 1] + bCounts[i];
}
int op1 = Integer.MAX_VALUE, op2 = Integer.MAX_VALUE;
for (int i = 0; i < 25; i++) {
int curOp1 = aLength - aCountsPrefix[i] + bLength - bCountsSuffix[i + 1];
int curOp2 = aLength - aCountsSuffix[i + 1] + bLength - bCountsPrefix[i];
op1 = Math.min(op1, curOp1);
op2 = Math.min(op2, curOp2);
}
int op3 = aLength - aMaxCount + bLength - bMaxCount;
return Math.min(Math.min(op1, op2), op3);
}
}