找到获得“好”字符串的最小移动次数

Question

当且仅当“字符串中的所有不同字符重复相同次数”时，称字符串为良好字符串。

现在，给定一个长度为n的字符串，我们必须在这个字符串中进行的最小更改次数是多少，这样字符串就变得正常了。

注意：我们只允许使用小写英文字母，我们可以将任何字母更改为任何其他字母。

示例：让String为yyxzzxxx

那么这里的答案是2。

说明：一种可能的解决方案YYXYXX。我们已将2“z”更改为2“y”。现在“x”和“y”都重复了4次。

我的做法：

1. 对所有26个小写字母的出现处进行散列
2. 还要查找字符串中不同字母的数量
3. 对该散列数组进行排序，并开始检查字符串的长度是否可以被不同字符数整除。如果是，那么我们得到了答案
4. 否则将不同字符减少1

但对于某些结果，它给出了错误的答案，因为当删除一些未出现最短时间的字符时，它们可能会以较少的移动提供一个好的字符串。

那么如何解决这个问题呢。请帮忙。

限制条件：字符串的长度最多为2000。

我的做法：

string s;
    cin>>s;
    int hash[26]={0};

    int total=s.length();
    for(int i=0;i<26;i++){
        hash[s[i]-'a']++;
    }
    sort(hash,hash+total);
    int ans=0;
    for(int i=26;i>=1;i--){
        int moves=0;
        if(total%i==0){
            int eachshouldhave=total/i;
            int position=26;
            for(int j=1;j<26;j++){
                if(hash[j]>eachshouldhave && hash[j-1]<eachshouldhave){
                    position=j;
                    break;
                }
            }
            int extrasymbols=0;
            //THE ONES THAT ARE BELOW OBVIOUSLY NEED TO BE CHANGED TO SOME OTHER SYMBOL
            for(int j=position;j<26;j++){
                extrasymbols+=hash[j]-eachshouldhave;
            }
            //THE ONES ABOVE THIS POSITION NEED TO GET SOME SYMBOLS FROM OTHERS
            for(int j=0;j<position;j++){
                moves+=(eachshouldhave-hash[j]);
            }
            if(moves<ans)
            ans=moves;
        }
        else
        continue;
    }

Answer 1

以下内容应修复您的实现：

std::size_t compute_change_needed(const std::string& s)
{
    int count[26] = { 0 };

    for(char c : s) {
        // Assuming only valid char : a-z
        count[c - 'a']++;
    }
    std::sort(std::begin(count), std::end(count), std::greater<int>{});
    std::size_t ans = s.length();
    for(std::size_t i = 1; i != 27; ++i) {
        if(s.length() % i != 0) {
            continue;
        }
        const int expected_count = s.length() / i;
        std::size_t moves = 0;
        for(std::size_t j = 0; j != i; j++) {
            moves += std::abs(count[j] - expected_count);
        }
        ans = std::min(ans, moves);
    }
    return ans;
}