Skip to content

3389. Minimum Operations to Make Character Frequencies Equal 👍

  • Time: O(26n)=O(n)O(26n) = O(n)
  • Space: O(26)=O(1)O(26) = O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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]
Was this page helpful?