[C++ / Go] Sliding Window - O(n) time / O(26) space solution
Approach\n- Count the number of occurrences of each character and then sort them in ascending order.\n- Iterate l through the counting array cnt:\n    - Maintai
# Approach\n- Count the number of occurrences of each character and then sort them in ascending order.\n- Iterate `l` through the counting array `cnt`:\n    - Maintain a sliding window with 2 ends `l` and `r`, where `cnt[r] - cnt[l] <= k` and `r` is maximum.\n    - Here we perform deletions to ensure that all occurrences of each character are either reduced to `0` or remain within the range from `cnt[l]` to `cnt[l] + k`.\n        - The part from `0` to `l - 1`, all characters will be deleted all to 0.\n        - The part from `r + 1` to `25`, all characters will be deleted down to `cnt[l] + k` occurences.\n            - ![Screenshot 2024-03-20 at 12.03.28 AM.png](https://assets.leetcode.com/users/images/cfc4d96c-a331-45fb-9f3c-ab3e97da340b_1710867823.681536.png)\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int minimumDeletions(string word, int k) {\n        vector<int> cnt(26, 0);\n        for (char c : word)\n            cnt[c - \'a\']++;\n\n        sort(cnt.begin(), cnt.end());\n        \n        int res = INT_MAX;\n\n        int leftSum = 0;\n        int rightSum = 0;\n\n        int r = 25;\n        while (cnt[r] > cnt[0] + k) {\n            rightSum += cnt[25] - cnt[r];\n            r--;\n        }\n\n        for (int l = 0; l < 26; l++) {\n            if (l > 0)\n                leftSum += cnt[l - 1];\n\n            int m = cnt[l] + k;\n            while (r < 25 && cnt[r + 1] <= m) {\n                r++; \n                rightSum -= cnt[25] - cnt[r];\n            }\n            \n            res = min(res, leftSum + (25 - r) * (cnt[25] - m) - rightSum);\n        }\n        \n        return res;\n    }\n};\n```\n```Go []\nfunc minimumDeletions(word string, k int) int {\n    cnt := make([]int, 26)\n\tfor _, c := range word {\n\t\tcnt[c - \'a\']++\n\t}\n\n\tsort.Ints(cnt)\n\n\tres := len(word)\n\n\tleftSum := 0\n\trightSum := 0\n\n\tr := 25\n\tfor ; cnt[r] > cnt[0] + k; r-- {\n\t\trightSum += cnt[25] - cnt[r]\n\t}\n\n\tfor l := 0; l < 26; l++ {\n\t\tif l > 0 {\n\t\t\tleftSum += cnt[l - 1]\n\t\t}\n\n\t\tm := cnt[l] + k\n\t\tfor r < 25 && cnt[r + 1] <= m {\n\t\t\tr++\n\t\t\trightSum -= cnt[25] - cnt[r]\n\t\t}\n\n        tmp := leftSum + (25 - r) * (cnt[25] - m) - rightSum\n        if (res > tmp) {\n            res = tmp\n        }\n\t}\n\n\treturn res\n}\n```\n\n# Complexity\n- Time complexity: $O(n)$\n- Space complexity: $O(26)$
['Sliding Window', 'C++', 'Go']