DP | Alternative Approach | C++
It can be solved with simple brute force iteration. Here is an alternative approach whic uses basic dynamic programming\n# Intuition\nFor any two numbers of the
It can be solved with simple brute force iteration. Here is an alternative approach whic uses basic dynamic programming\n# Intuition\nFor any two numbers of the frequency array, there are two possibilities - either remove the smaller one or decrease the larger one.\n\n\n# Approach\nWrite a recursive code for the two by intialising two pointers - one at start and one at end of the sorted frequency array\n\nNOTE - It will be accepted without DP as well.\n\n# Complexity\n- Time complexity:\n- O(n) with dp\n- O(max(n,2^26)) without dp\n\n- Space complexity:\nO(26*26) = O(1)\n\n# Code\n```\nclass Solution {\npublic:\n    int fn(vector<int> &v, int k, int i,int j,vector<vector<int>> &dp){\n        if (dp[i][j] != -1) return dp[i][j];\n        int c1 = 0, c2 = 0; int z = v[j]-v[i];\n        if (z > k){\n            c1 += v[i]+fn(v,k,i+1,j,dp); // removing the smaller\n            c2 += (z-k)+fn(v,k,i,j-1,dp); // decreasing the larger\n        } else {\n            return 0;\n        }\n        return dp[i][j] = min(c1,c2);\n    }\n    int minimumDeletions(string word, int k) {\n        unordered_map<char,int> m;\n        for (auto x: word)m[x]++;\n        vector<int> v;\n        for (auto x: m)v.push_back(x.second);\n        if (v.size() <= 1) return 0; // if only one kind of character is present in the string return zero\n        sort(v.begin(),v.end());\n        int i = 0, j = v.size()-1;\n        vector<vector<int>> dp(26,vector<int>(26,-1));\n        int ans = fn(v,k,i,j,dp);\n        return ans;\n    }\n};\n```
['C++']