Easy C++ Prefix sum + Greedy
\n\n# Code\n\nclass Solution {\npublic:\n    int minimumDeletions(string word, int k) {\n        int n = word.size();\n        if(n<=1) return 0;\n        vecto
\n\n# Code\n```\nclass Solution {\npublic:\n    int minimumDeletions(string word, int k) {\n        int n = word.size();\n        if(n<=1) return 0;\n        vector<int>alpha(26,0);\n        vector<int>prefix(26,0);\n        for(auto ch: word){\n            alpha[ch-\'a\']++;\n        }\n\n        sort(alpha.begin(),alpha.end());\n        prefix[0] = alpha[0];\n        for(int i=1;i<26;i++){\n            prefix[i] = prefix[i-1]+alpha[i];\n        }\n        int sum = 0;\n        for(int j=0;j<26;j++) {\n            sum+=alpha[j];\n        }\n        int i=0;\n        int ans = INT_MAX;\n\n        while(alpha[i]==0){\n            i++;\n        }\n        for(;i<25;i++){\n            auto index = upper_bound(alpha.begin(),alpha.end(),alpha[i]+k) - alpha.begin();\n            int cur = prefix[25] - prefix[index-1];\n            if(i>0) cur+= prefix[i-1];\n            cur-= (26-index)*(k+alpha[i]);\n            ans = min(ans,cur);\n        }\n        ans = min(ans,sum-alpha[25]);\n\n        return ans;\n    }\n};\n```
['C++']