Easy to Understand O(N) TC and O(1) SC Beats 100%
https://leetcode.com/problems/minimum-deletions-to-make-string-k-special/submissions/1206029598/\n# Intuition\n Describe your first thoughts on how to solve thi
[https://leetcode.com/problems/minimum-deletions-to-make-string-k-special/submissions/1206029598/]()\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIntution is to select a non zero frequency and make all the other frequencies to be in the range of `[frequency, frequency + k]`\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSee psuedo code in comments\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int minimumDeletions(string word, int k) {\n        /* \n            1. calculate the character frequency\n            2. Intution is to select a non zero frequency(freqSelected) and make all the other to be in the [freqSelected, freqSelected + k]\n                a. if freq[i] < freqSelected => you can\'t select freq[i] so add to cost\n                b. if freqSelected <= freq[i] <= freqSelected + k => aleady in the range no additional cost required\n                c. if freqSelected > freq[i] + k => minimum cost is to set freq[i] = freqSelected + k\n                    E.g freqSelected = 5, k = 4\n                        1 2 3 4 5 6 7 8 9 10\n                        1 < 5 => cost = 1\n                        2 < 5 => cost = 1 + 2 = 3\n                        3 < 5 => cost = 3 + 3 = 6\n                        4 < 5 => cost = 6 + 4 = 10\n                        5 belongs to [5, 9] => cost = 10 // already in range\n                        6 belongs to [5, 9] => cost = 10 // already in range\n                        7 belongs to [5, 9] => cost = 10 // already in range\n                        8 belongs to [5, 9] => cost = 10 // already in range\n                        9 belongs to [5, 9] => cost = 10 // already in range\n                        10 > (5 + 4) => cost = 10 + (10 - (5 + 4)) = 10 + 1 = 11\n            3. repeat step2 for all non-zero frequencies\n            4. return minimum cost calculated\n\n            TC - O(N) + O(26 * 26) = O(N) where N is length of string\n            SC - O(1) since fq vector is of constant space\n        */\n        /* Count frequency of character in word (a-z) */\n        vector<int> fq(26, 0);\n        for(auto i : word) fq[i - \'a\']++;\n        int miny = INT_MAX;\n        for(int i = 0; i < 26; i++){\n            int c = 0;\n            if(fq[i] == 0) continue;\n            /* freqSelected is fq[i] */\n            for(int j = 0; j < 26; j++){\n                if(fq[j] < fq[i]) c += fq[j];           /* fq[j] < freqSelected */\n                else if(fq[j] - fq[i] <= k) continue;   /* freqSelected <= fq[j] <= freqSelected + k */\n                else c += fq[j] - fq[i] - k;            /* fq[j] > freqSelected + k */\n            }\n            miny = min(miny, c);\n        }\n        return miny;\n    }\n};\n```
['C++']