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

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

## Level

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);
}
}
```