Minimum Operations to Make Character Frequencies Equal

Hard

Google

1 view

Topics:

Strings

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

What is the most efficient algorithm for solving this problem? What is the Big O time and space complexity?

Minimum Operations to Make Character Frequencies Equal

Hard

Google

1 view

Topics:

Strings

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

What is the most efficient algorithm for solving this problem? What is the Big O time and space complexity?

Solution

Naive Approach

A brute force approach would involve trying all possible combinations of operations (delete, insert, change) to make the string "good". This would be highly inefficient due to the exponential nature of possible combinations.

For each position, we have choices. Delete, Insert, or Change. This quickly explodes computationally.
Big(O) Run-time: Exponential O(3^n), where n is the length of the string.
Big(O) Space usage: O(n) for the recursion depth, potentially higher if storing all combinations.

Optimal Approach

An optimal approach involves analyzing the frequency of each character in the string. The key insight is that to make the string "good", all characters must have the same frequency. We can try all possible frequencies and calculate the minimum number of operations required to achieve that frequency for each character.

Count Frequencies: Count the occurrences of each character in the string.
Iterate through Possible Frequencies: Loop through all possible frequencies from 1 to the length of the string.
Calculate Operations: For each possible frequency, calculate the operations needed to make each character's frequency equal to the target frequency. The cost is abs(actual_frequency - target_frequency). If actual_frequency > target_frequency, this is deletion, if actual_frequency < target_frequency, this is insert or change (it's cheaper to insert). Changing a character costs 1. Insertion cost is 1.
Minimize: Track and return the minimum number of operations across all frequencies.

Edge Cases:

Empty string. Return 0.
String with only one character. Return 0.
All characters are the same. Return 0.

Code Example (Python):

from collections import Counter

def min_operations(s):
    n = len(s)
    counts = Counter(s)
    min_ops = float('inf')

    for target_freq in range(1, n + 1):
        ops = 0
        for char in 'abcdefghijklmnopqrstuvwxyz':
            actual_freq = counts[char]
            ops += abs(actual_freq - target_freq)
        min_ops = min(min_ops, ops)

    return min_ops

Big(O) Run-time: O(26 * n), where n is the length of the string. The outer loop iterates up to n, and the inner loop iterates through the alphabet (26 characters).
Big(O) Space usage: O(1). The Counter object uses a fixed amount of space (26 characters).

Solution

Naive Approach

For each position, we have choices. Delete, Insert, or Change. This quickly explodes computationally.
Big(O) Run-time: Exponential O(3^n), where n is the length of the string.
Big(O) Space usage: O(n) for the recursion depth, potentially higher if storing all combinations.

Optimal Approach

Count Frequencies: Count the occurrences of each character in the string.
Iterate through Possible Frequencies: Loop through all possible frequencies from 1 to the length of the string.
Calculate Operations: For each possible frequency, calculate the operations needed to make each character's frequency equal to the target frequency. The cost is abs(actual_frequency - target_frequency). If actual_frequency > target_frequency, this is deletion, if actual_frequency < target_frequency, this is insert or change (it's cheaper to insert). Changing a character costs 1. Insertion cost is 1.
Minimize: Track and return the minimum number of operations across all frequencies.

Edge Cases:

Empty string. Return 0.
String with only one character. Return 0.
All characters are the same. Return 0.

Code Example (Python):

from collections import Counter

def min_operations(s):
    n = len(s)
    counts = Counter(s)
    min_ops = float('inf')

    for target_freq in range(1, n + 1):
        ops = 0
        for char in 'abcdefghijklmnopqrstuvwxyz':
            actual_freq = counts[char]
            ops += abs(actual_freq - target_freq)
        min_ops = min(min_ops, ops)

    return min_ops

Big(O) Run-time: O(26 * n), where n is the length of the string. The outer loop iterates up to n, and the inner loop iterates through the alphabet (26 characters).
Big(O) Space usage: O(1). The Counter object uses a fixed amount of space (26 characters).