Minimum Operations to Make Character Frequencies Equal

Minimum Operations to Make Character Frequencies Equal - 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.

Input & Output

Example 1 — Simple Case

$ Input: s = "abc"

› Output: 0

💡 Note: All characters already appear exactly once, so the string is already good. No operations needed.

Example 2 — Need Balancing

$ Input: s = "aab"

› Output: 1

💡 Note: We have a=2, b=1. To make all frequencies equal to 1, we need 1 operation: change one 'a' to 'c' to get "acb" where a=1, b=1, c=1.

Example 3 — Multiple Operations

$ Input: s = "aaaa"

› Output: 3

💡 Note: We have a=4. To make it good, we can change to get a=1, b=1, c=1, d=1. This requires 3 operations: change 'a'→'b', 'a'→'c', 'a'→'d'.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Count frequency of each character in string

Find Target

Determine optimal target frequency for all characters

Apply Operations

Use delete, insert, change operations to reach target

Key Takeaway

🎯 Key Insight: Test only promising target frequencies based on existing character counts and use transformation chains to minimize operations

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is to enumerate possible target frequencies and use character transformation chains (a→b→c→...) to minimize operations. The optimal approach only tests promising target frequencies based on existing character counts rather than all possibilities. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Frequency Enumeration	O(n × 26)	O(1)	Count frequencies first, then optimize target selection using character transformation chains
Brute Force Enumeration	O(n²)	O(1)	Try all possible target frequencies from 0 to string length
Smart Target Selection	O(n)	O(1)	Only test promising target frequencies based on existing character counts and mathematical bounds

Optimized Frequency Enumeration — Algorithm Steps

Count frequency of each character in the input string
For each possible target frequency, calculate operations needed
Use character transformation chains (a→b→c→...) to minimize operations
Consider deletes, inserts, and character changes optimally
Return minimum operations across all target frequencies

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

a=2, b=1, c=0 for input 'aab'

Try Target=1

Need: a=1, b=1, c=1

Transform Chain

Excess 'a' can become 'b', then 'c'

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(char* s) {
    int freq[26] = {0};
    int len = strlen(s);
    
    for (int i = 0; i < len; i++) {
        freq[s[i] - 'a']++;
    }
    
    int minOps = INT_MAX;
    
    // Try different target frequencies
    for (int target = 0; target <= len; target++) {
        int ops = 0;
        int tempFreq[26];
        memcpy(tempFreq, freq, sizeof(freq));
        
        // Process characters from 'z' to 'a' to handle transformations
        for (int i = 25; i >= 0; i--) {
            if (tempFreq[i] > target) {
                int excess = tempFreq[i] - target;
                if (i > 0) {
                    // Can transform excess to previous character
                    tempFreq[i-1] += excess;
                } else {
                    // Must delete excess 'a' characters
                    ops += excess;
                }
                tempFreq[i] = target;
            } else if (tempFreq[i] < target) {
                int needed = target - tempFreq[i];
                ops += needed;  // Insert operations
            }
        }
        
        if (ops < minOps) {
            minOps = ops;
        }
    }
    
    return minOps;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 26)

For each of O(n) target frequencies, we process 26 characters with transformation chains

✓ Linear Growth

Space Complexity

O(1)

Only using fixed-size arrays for 26 characters

✓ Linear Space

25.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Frequency Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler