LeetCode 1737: Change Minimum Characters to Satisfy One of Three Conditions
Problem Description
Explanation:
To solve this problem, we can iterate over all possible letters and find the best way to achieve one of the three conditions. We need to consider changing letters in both strings a and b to satisfy the conditions. We can calculate the required operations for each condition separately and return the minimum number of operations needed.
- Calculate the number of operations needed to make every letter in
astrictly less than every letter inb. - Calculate the number of operations needed to make every letter in
bstrictly less than every letter ina. - Calculate the number of operations needed to make both
aandbconsist of only one distinct letter. - Return the minimum number of operations among the three conditions.
Solutions
class Solution {
public int minCharacters(String a, String b) {
int[] freqA = new int[26];
int[] freqB = new int[26];
for (char c : a.toCharArray()) {
freqA[c - 'a']++;
}
for (char c : b.toCharArray()) {
freqB[c - 'a']++;
}
int minOps = Integer.MAX_VALUE;
for (int i = 0; i < 26; i++) {
minOps = Math.min(minOps, a.length() + b.length() - freqA[i] - freqB[i]);
if (i > 0) {
freqA[i] += freqA[i - 1];
freqB[i] += freqB[i - 1];
}
if (i < 25) {
minOps = Math.min(minOps, a.length() - freqA[i] + freqB[i]);
minOps = Math.min(minOps, b.length() - freqB[i] + freqA[i]);
}
}
return minOps;
}
}Loading editor...