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 inb
in the alphabet. - Every letter in
b
is strictly less than every letter ina
in the alphabet. - Both
a
andb
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
andb
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);
}
}