3389. Minimum Operations to Make Character Frequencies Equal LeetCode Solution
In this guide, you will get 3389. Minimum Operations to Make Character Frequencies Equal LeetCode Solution with the best time and space complexity. The solution to Minimum Operations to Make Character Frequencies Equal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Operations to Make Character Frequencies Equal
You are given a string s.
A string t is called good if all characters of t occur the same number of times.
You can perform the following operations any number of times:
Delete a character from s.
Insert a character in s.
Change a character in s to its next letter in the alphabet.
Note that you cannot change ‘z’ to ‘a’ using the third operation.
Return the minimum number of operations required to make s good.
Example 1:
Input: s = “acab”
Output: 1
Explanation:
We can make s good by deleting one occurrence of character ‘a’.
Example 2:
Input: s = “wddw”
Output: 0
Explanation:
We do not need to perform any operations since s is initially good.
Example 3:
Input: s = “aaabc”
Output: 2
Explanation:
We can make s good by applying these operations:
Change one occurrence of ‘a’ to ‘b’
Insert one occurrence of ‘c’ into s
3 <= s.length <= 2 * 104
s contains only lowercase English letters.
Complexity Analysis
Time Complexity: O(26n) = O(n)
Space Complexity: O(26) = O(1)
3389. Minimum Operations to Make Character Frequencies Equal LeetCode Solution in C++
class Solution {
public:
int makeStringGood(string s) {
int ans = s.length();
vector<int> count(26);
for (const char c : s)
++count[c - 'a'];
const int mx = ranges::max(count);
for (int target = 1; target <= mx; ++target)
ans = min(ans, getMinOperations(count, target));
return ans;
}
private:
int getMinOperations(const vector<int>& count, int target) {
// dp[i] := the minimum number of operations to make the frequency of
// (i..25)-th (0-indexed) letters equal to `target`.
vector<int> dp(27);
for (int i = 25; i >= 0; --i) {
// 1. Delete all the i-th letters.
const int deleteAllToZero = count[i];
// 2. Insert/delete the i-th letters to have `target` number of letters.
const int deleteOrInsertToTarget = abs(target - count[i]);
dp[i] = min(deleteAllToZero, deleteOrInsertToTarget) + dp[i + 1];
if (i + 1 < 26 && count[i + 1] < target) {
const int nextDeficit = target - count[i + 1];
// Make the frequency of the i-th letter equal to the `target` or 0.
const int needToChange =
count[i] > target ? count[i] - target : count[i];
const int changeToTarget =
nextDeficit > needToChange
// 3. Change all the i-th letters to the next letter and then
// insert the remaining deficit for the next letter.
? needToChange + (nextDeficit - needToChange)
// 4. Change `nextDeficit` i-th letters to the next letter and
// then delete the remaining i-th letters.
: nextDeficit + (needToChange - nextDeficit);
dp[i] = min(dp[i], changeToTarget + dp[i + 2]);
}
}
return dp[0];
}
}; /* code provided by PROGIEZ */
3389. Minimum Operations to Make Character Frequencies Equal LeetCode Solution in Java
class Solution {
public int makeStringGood(String s) {
int ans = s.length();
int[] count = new int[26];
for (final char c : s.toCharArray())
++count[c - 'a'];
final int maxCount = Arrays.stream(count).max().getAsInt();
for (int target = 1; target <= maxCount; ++target)
ans = Math.min(ans, getMinOperations(count, target));
return ans;
}
private int getMinOperations(int[] count, int target) {
// dp[i] represents the minimum number of operations to make the frequency of
// (i..25)-th (0-indexed) letters equal to `target`.
int[] dp = new int[27];
for (int i = 25; i >= 0; --i) {
// 1. Delete all the i-th letters.
int deleteAllToZero = count[i];
// 2. Insert/delete the i-th letters to have `target` number of letters.
int deleteOrInsertToTarget = Math.abs(target - count[i]);
dp[i] = Math.min(deleteAllToZero, deleteOrInsertToTarget) + dp[i + 1];
if (i + 1 < 26 && count[i + 1] < target) {
final int nextDeficit = target - count[i + 1];
// Make the frequency of the i-th letter equal to the `target` or 0.
final int needToChange = count[i] <= target ? count[i] : count[i] - target;
final int changeToTarget = (nextDeficit > needToChange)
// 3. Change all the i-th letters to the next letter and then
// insert the remaining deficit for the next letter.
? needToChange + (nextDeficit - needToChange)
// 4. Change `nextDeficit` i-th letters to the next letter
// and then delete the remaining i-th letters.
: nextDeficit + (needToChange - nextDeficit);
dp[i] = Math.min(dp[i], changeToTarget + dp[i + 2]);
}
}
return dp[0];
}
} // code provided by PROGIEZ
3389. Minimum Operations to Make Character Frequencies Equal LeetCode Solution in Python
class Solution:
def makeStringGood(self, s: str) -> int:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
return min(self._getMinOperations(count, target)
for target in range(1, max(count) + 1))
def _getMinOperations(self, count: list[int], target: int) -> int:
# dp[i] represents the minimum number of operations to make the frequency of
# (i..25)-th (0-indexed) letters equal to `target`.
dp = [0] * 27
for i in range(25, -1, -1):
# 1. Delete all the i-th letters.
deleteAllToZero = count[i]
# 2. Insert/delete the i-th letters to have `target` number of letters.
deleteOrInsertToTarget = abs(target - count[i])
dp[i] = min(deleteAllToZero, deleteOrInsertToTarget) + dp[i + 1]
if i + 1 < 26 and count[i + 1] < target:
nextDeficit = target - count[i + 1]
# Make the frequency of the i-th letter equal to the `target` or 0.
needToChange = count[i] if count[i] <= target else count[i] - target
changeToTarget = (
# 3. Change all the i-th letters to the next letter and then
# insert the remaining deficit for the next letter.
needToChange + (nextDeficit - needToChange) if nextDeficit > needToChange
# 4. Change `nextDeficit` i-th letters to the next letter and
# then delete the remaining i-th letters.
else nextDeficit + (needToChange - nextDeficit)
)
dp[i] = min(dp[i], changeToTarget + dp[i + 2])
return dp[0] # code by PROGIEZ
