[C++][Prefix sum]
\nclass Solution {\npublic:\n    int minimumDeletions(string word, int k) {\n        /*\n        a->1 b->2 c->3 d->5\n        */\n        vector<int> cnt(26);\n
```\nclass Solution {\npublic:\n    int minimumDeletions(string word, int k) {\n        /*\n        a->1 b->2 c->3 d->5\n        */\n        vector<int> cnt(26);\n        for(const auto w: word) cnt[w-\'a\']++;\n        \n        vector<int> dp;\n        for (int i=0;i<26;i++) if (cnt[i]>0) dp.push_back(cnt[i]);\n        \n        sort(dp.begin(),dp.end());\n        \n        vector<int> prefixSum(dp.size()+1);\n        for (int i=0;i<dp.size();i++) prefixSum[i+1] = prefixSum[i] + dp[i];\n        \n        int ans=INT_MAX,ri=0,leftAdj=0,rightAdj=0;\n        for(int i=0;i<dp.size();i++){\n            //li = lower_bound(dp.begin(),dp.end(),dp[i]-k)-dp.begin();\n            ri = upper_bound(dp.begin(),dp.end(),dp[i]+k)-dp.begin();\n            leftAdj = prefixSum[i];\n            rightAdj = prefixSum.back()-prefixSum[ri]-(dp[i]+k)*(dp.size()-ri);\n            ans = min(ans,leftAdj + rightAdj);\n            //cout << i << " " << dp[i] << " " << li << " " << ri << " " << leftAdj << " " << rightAdj << endl;\n        }\n        return ans;\n        \n    }\n};\n```
[]