Dynamic Programming Easy to Understand Solution
Intuition\nThe function f is recursively called to find the minimum number of deletions required. It considers the leftmost and rightmost characters \nIf the di
# Intuition\nThe function f is recursively called to find the minimum number of deletions required. It considers the leftmost and rightmost characters \nIf the difference between their frequencies is less equal to k, no need to check further.\nElse perform deletion\nDeletion can be done in two different ways\n- Either delete the lower frequency element\n- Or remove required appearances from higher frequency element\n\n# Approach\n- Count frequency of every character and store in array\n- Sort this array\n- Call the function\n\n# Complexity\n- Time complexity:\n**O(N^2)**  again n is just 26\n\n- Space complexity:\n**O(26) = O(1)**\n\n# Code\n```\nclass Solution {\nprivate:\n    int dp[26][26];\n    int f(vector<int>&freq, int l, int r, int k){\n        if(l==r)return 0;\n        if(freq[r]-freq[l]<=k)return 0;\n        if(dp[l][r]!=-1)return dp[l][r];\n        \n        return dp[l][r]=min(freq[l]+f(freq,l+1,r,k), freq[r]-(freq[l]+k)+f(freq,l,r-1,k));\n    }\npublic:\n    int minimumDeletions(string word, int k) {\n        vector<int>freq(26,0);\n        for(int i=0; i<word.size(); i++){\n            freq[word[i]-\'a\']++;\n        }\n        sort(freq.begin(),freq.end());\n        memset(dp,-1,sizeof(dp));\n        return f(freq,0,25,k);\n    }\n};\n```
['Dynamic Programming', 'Sorting', 'C++']