Minimum number of steps to equalize distinct character of the string

Admin 1
Viewed 311

I'm trying to write this program that asks for user input of string, my job is to print out the minimum number of steps required to equalize the frequency of distinct characters of the string.
Example
Input

6
aba  
abba  
abbc  
abbbc  
codedigger  
codealittle

Output

1
0
1
2
2
3

Here is my program:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

int main()
{
    unordered_map<char, int >m;
    vector<int> vec1, vec2;
    string s;
    int n;

    cin >> n;
    cin.ignore();

    for (int i = 0; i < n; ++i)
    {
        m.clear();
        vec1.clear();
        getline(cin, s);
        for (int i = 0; i < s.size(); i++)
            m[s[i]]++;

        for (auto itr : m)
            vec1.push_back(itr.second);

        sort(vec1.begin(), vec1.end());

        int mid = vec1[vec1.size() / 2];
        int ans = 0;

        for (auto itr : vec1)
            ans += abs(mid - itr);

        vec2.push_back(ans);
    }
    for (int i = 0; i < vec2.size(); ++i)
        cout << vec2[i] << endl;
}

What I tried to do is for each test case:

  • Using an unordered_map to count the frequency of the characters of the string.
  • Push the key values of the map to a vector.
  • Sort the vector in ascending order.
  • Calculate the middle element of the vector to equalize the distinct characters with as least steps as possible.
  • The result will add the difference between the middle element with the current element.
  • Push the result to another vector and print it.

But my result is wrong at test case number 5:

1  
0  
1  
2  
3  // The actual result is 2
3

I don't understand why I get the wrong result, can anyone help me with this? Thanks for your help!

algorithm c++
2 Answers

The issue is that your algorithm is not finding the optimal number of steps.

Consider the string you obtained an incorrect answer for: codedigger. It has 4 letters of frequency 1 (coir) and 3 letters of frequency 2 (ddeegg). The optimal way is not to convert half the letters of frequency 2 into some new character (not present in the string) to make all frequency 1. From my understanding, your implementation is counting the number of steps that this would require. Instead, consider this:

c[o]dedigge[r]

If I replace o with c and r with i, I obtain:

ccdediggei

which already has equalized character frequencies. You will note that I only performed 2 edits.

So without giving you a solution, I believe this might still answer your question? Perhaps with this in mind, you can come up with a different algorithm that is able to find the optimal number of edits.

user_105591420

Your code correctly measures the frequencies of each letter, as the important information.

But then, there were mainly two issues:

  • The main target value (final equalized frequency) is not necessarily equal to the median value. In particular, this value must divide the total number of letters
  • For a given targeted height value, your calculation of the number of steps is not correct. You must pay attention not to count twice the same mutation. Moreover, the general formula is different, depending the final number of different letters is equal, less or higher than the original number of letters.

The following code focuses on correctness, not on efficiency too much. It considers all the possible values of the targeted height (frequency), i.e. all the divisors of the total number of letters.

If efficiency is really a concern (not mentioned in the post), then for example one could consider that the best value is unlikely to be very far from the initial average frequency value.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <unordered_map>


//  calculates the number of steps for a given target
//  This code assumes that the frequencies are sorted in descending order. 

int n_steps (std::vector<int>& freq, int target, int nchar) {
    int sum = 0;
    int n = freq.size();
    int m = nchar/target;   // new number of characters
    
    int imax = std::min (n, m);
    for (int i = 0; i < imax; ++i) {
        sum += std::abs (freq[i] - target);
    }
    for (int i = imax; i < n; ++i) {
        sum += freq[i];
    }
    
    if (m > n) sum += m-n;
    sum /= 2;
    
    return sum;
}

int main() {
    std::unordered_map<char, int >m;
    std::vector<int> vec1, vec2;
    std::string s;
    int n;

    std::cin >> n;
    std::cin.ignore();

    for (int i = 0; i < n; ++i)
    {
        m.clear();
        vec1.clear();
        //getline(cin, s);
        std::cin >> s;
        for (int i = 0; i < s.size(); i++)
            m[s[i]]++;

        for (auto itr : m)
            vec1.push_back(itr.second);

        sort(vec1.begin(), vec1.end(), std::greater<int>());
        
        int nchar = s.size();
        int n_min_oper = nchar+1;
        for (int target = 1; target <= nchar; ++target) {
            if (nchar % target) continue;
            int n_oper = n_steps (vec1, target, nchar);
            if (n_oper < n_min_oper) n_min_oper = n_oper;
        }
        vec2.push_back(n_min_oper);
    }
    for (int i = 0; i < vec2.size(); ++i)
        std::cout << vec2[i] << std::endl;
}
user_105533410
Related