Problem

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.

Examples

Example 1

1
2
3
4

Input: "acab"
Output: 1
Explanation:
We can make `s` good by deleting one occurrence of character `'a'`.

Example 2

1
2
3
4

Input: "wddw"
Output: 0
Explanation:
We do not need to perform any operations since `s` is initially good.

Example 3

1
2
3
4
5
6

Input: "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`

Constraints

  • 3 <= s.length <= 2 * 10^4
  • s contains only lowercase English letters.

Solution

Method 1 – Enumeration & Frequency Balancing

Intuition

To make all character frequencies equal, we can enumerate all possible target frequencies and number of distinct characters, and for each, calculate the minimum operations needed to reach that configuration using insert, delete, and change operations.

Approach

  1. Count the frequency of each character in s.
  2. For each possible number of distinct characters (from 1 to 26):
    • For each possible target frequency (from 1 up to max possible):
      • Calculate the cost to make exactly that many characters have the target frequency, and all others have zero.
  3. For each configuration, compute the cost:
    • If a character has more than target frequency, delete or change.
    • If less, insert or change.
    • If not present, insert.
  4. Return the minimum cost among all configurations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int minOperations(string s) {
        vector<int> freq(26, 0);
        for (char c : s) freq[c - 'a']++;
        int ans = INT_MAX, n = s.size();
        for (int chars = 1; chars <= 26; ++chars) {
            for (int f = 1; f * chars <= n; ++f) {
                vector<int> v = freq;
                sort(v.rbegin(), v.rend());
                int cost = 0;
                for (int i = 0; i < chars; ++i) cost += abs(v[i] - f);
                for (int i = chars; i < 26; ++i) cost += v[i];
                ans = min(ans, cost);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int minOperations(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) freq[c - 'a']++;
        int ans = Integer.MAX_VALUE, n = s.length();
        for (int chars = 1; chars <= 26; chars++) {
            for (int f = 1; f * chars <= n; f++) {
                int[] v = freq.clone();
                Arrays.sort(v);
                int cost = 0;
                for (int i = 0; i < chars; i++) cost += Math.abs(v[25-i] - f);
                for (int i = chars; i < 26; i++) cost += v[25-i];
                ans = Math.min(ans, cost);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from collections import Counter
class Solution:
    def minOperations(self, s: str) -> int:
        freq = [0]*26
        for c in s:
            freq[ord(c)-97] += 1
        n = len(s)
        ans = float('inf')
        for chars in range(1, 27):
            for f in range(1, n//chars+1):
                v = sorted(freq, reverse=True)
                cost = sum(abs(v[i]-f) for i in range(chars)) + sum(v[i] for i in range(chars, 26))
                ans = min(ans, cost)
        return ans
 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

func minOperations(s string) int {
    freq := make([]int, 26)
    for _, c := range s {
        freq[c-'a']++
    }
    n := len(s)
    ans := 1 << 30
    for chars := 1; chars <= 26; chars++ {
        for f := 1; f*chars <= n; f++ {
            v := append([]int{}, freq...)
            sort.Sort(sort.Reverse(sort.IntSlice(v)))
            cost := 0
            for i := 0; i < chars; i++ {
                if v[i] > f {
                    cost += v[i] - f
                } else {
                    cost += f - v[i]
                }
            }
            for i := chars; i < 26; i++ {
                cost += v[i]
            }
            if cost < ans {
                ans = cost
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun minOperations(s: String): Int {
        val freq = IntArray(26)
        for (c in s) freq[c - 'a']++
        val n = s.length
        var ans = Int.MAX_VALUE
        for (chars in 1..26) {
            for (f in 1..(n/chars)) {
                val v = freq.sortedDescending()
                var cost = 0
                for (i in 0 until chars) cost += kotlin.math.abs(v[i] - f)
                for (i in chars until 26) cost += v[i]
                ans = minOf(ans, cost)
            }
        }
        return ans
    }
}
 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

impl Solution {
    pub fn min_operations(s: String) -> i32 {
        let mut freq = vec![0; 26];
        for c in s.chars() {
            freq[c as usize - 'a' as usize] += 1;
        }
        let n = s.len();
        let mut ans = i32::MAX;
        for chars in 1..=26 {
            for f in 1..=n/chars {
                let mut v = freq.clone();
                v.sort_by(|a, b| b.cmp(a));
                let mut cost = 0;
                for i in 0..chars {
                    cost += (v[i] as i32 - f as i32).abs();
                }
                for i in chars..26 {
                    cost += v[i] as i32;
                }
                if cost < ans { ans = cost; }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    minOperations(s: string): number {
        const freq = Array(26).fill(0);
        for (const c of s) freq[c.charCodeAt(0) - 97]++;
        const n = s.length;
        let ans = Number.MAX_SAFE_INTEGER;
        for (let chars = 1; chars <= 26; chars++) {
            for (let f = 1; f * chars <= n; f++) {
                const v = [...freq].sort((a, b) => b - a);
                let cost = 0;
                for (let i = 0; i < chars; i++) cost += Math.abs(v[i] - f);
                for (let i = chars; i < 26; i++) cost += v[i];
                ans = Math.min(ans, cost);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(26 * n^2) — For each possible number of distinct characters and frequency, we scan and sort the frequency array.
  • 🧺 Space complexity: O(1) — Only a few arrays of size 26 are used.