Input: a ="aba", b ="caa"Output: 2Explanation: Consider the best way to make each condition true:1) Change b to "ccc"in2 operations, then every letter in a is less than every letter in b.2) Change a to "bbb" and b to "aaa"in3 operations, then every letter in b is less than every letter in a.3) Change a to "aaa" and b to "aaa"in2 operations, then a and b consist of one distinct letter.The best way was done in2operations(either condition 1 or condition 3).
Intuition:
We want to minimize the number of changes to make one of three conditions true. For the first two conditions, we can use prefix sums to efficiently count how many characters need to be changed to make all of one string less than all of the other. For the third condition, we count the most frequent character in both strings and try to make all characters the same.
Approach:
Count the frequency of each letter (a-z) in both strings.
Build prefix sums for both frequency arrays.
For conditions 1 and 2, try every possible split point (from ‘a’+1 to ‘z’) and calculate the number of changes needed.
For condition 3, try every letter and count how many changes are needed to make both strings consist of only that letter.
classSolution {
publicintminCharacters(String a, String b) {
int[] ca =newint[26], cb =newint[26];
for (char ch : a.toCharArray()) ca[ch -'a']++;
for (char ch : b.toCharArray()) cb[ch -'a']++;
int n = a.length(), m = b.length(), ans = n + m;
int[] pa =newint[27], pb =newint[27];
for (int i = 0; i < 26; i++) {
pa[i+1]= pa[i]+ ca[i];
pb[i+1]= pb[i]+ cb[i];
}
for (int i = 1; i < 26; i++) {
ans = Math.min(ans, n - pa[i]+ pb[i]);
ans = Math.min(ans, m - pb[i]+ pa[i]);
}
for (int i = 0; i < 26; i++) {
ans = Math.min(ans, n + m - ca[i]- cb[i]);
}
return ans;
}
}
classSolution:
defminCharacters(self, a: str, b: str) -> int:
ca = [0] *26 cb = [0] *26for ch in a:
ca[ord(ch) - ord('a')] +=1for ch in b:
cb[ord(ch) - ord('a')] +=1 n, m = len(a), len(b)
pa = [0] *27 pb = [0] *27for i in range(26):
pa[i+1] = pa[i] + ca[i]
pb[i+1] = pb[i] + cb[i]
ans = n + m
for i in range(1, 26):
ans = min(ans, n - pa[i] + pb[i])
ans = min(ans, m - pb[i] + pa[i])
for i in range(26):
ans = min(ans, n + m - ca[i] - cb[i])
return ans