3 solutions | Greedy, DFS/Rec, Memoization (DP)
Solution-1: Greedy (WA -- 688 / 732 TCs passed -- 93.98%)\n+ IDEA: At each stage, we\'re greedily picking the smallest required change. i.e either mn (min eleme
# Solution-1: Greedy (WA -- 688 / 732 TCs passed -- 93.98%)\n+ **IDEA:** At each stage, we\'re greedily picking the smallest required change. i.e either `mn` (min element) or `mx-mn-k` (removing diff from max element).\n+ **NOTE:** Kindly note that this solution only passes 93.98% of TCs. Intention behind sharing this solution is to: 1) Make you aware why greedy doesn\'t work here 2) How I came to the final solution.\n+ Greedy solution doesn\'t work here because there would be cases where removing min element would cause the result to be greater. Hence we would have to consider all possibilities to decide the answer.\nI hope this helps!\n\t### Complexity:\n\t+ **Time:** O(26 ^ 2)\n\t+ **Space:** O(26) --> **O(1)**\n\n\n# Solution-2: DFS/Recursion (AC -- 732/732 TCs Passed. -- 100%)\n+ **IDEA:** Consider all possibilities. Try removing/deleting from both ends -- min end and max end. \n\t### Complexity:\n\t+ **Time:** O(2^26) --> **O(10^7)**\n\t+ **Space:** O(26) --> **O(1)**\n# Solution-3: Memoization (DP) -- (AC -- 732/732 TCs Passed. -- 100%)\n+ **IDEA:** Memoize/store the result so that we do not compute the same sub problem again and again.\n\t### Complexity:\n\t+ **Time:** O(26^2) \n\t+ **Space:** O(26^2)\n# CODE:\n\n```\nclass Solution {\npublic:\n    // SOL-1: GREEDY -- WA -- 688 / 732 TCs passed -- 93.98%\n    int minimumDeletions(string word, int k) \n    {\n        vector<int> a(26, 0);\n        for ( const char& c: word )\n            a[c-\'a\']++;\n        \n        // SOL-1: GREEDY -- WA -- 688 / 732 TCs passed -- 93.98%\n        // return greedy(a, k);\n        \n        // SOL-2: dfs/rec -- TC: O(2^26) -> O(10^7), SC: O(26) -- 732/732 TCs Passed.\n        // sort(a.begin(), a.end());\n        // return dfs(a, k, 0, a.size()-1);\n        \n        // SOL-3: DP -- MEMOIZATION -- TOP DOWN DP -- TC: O(26^2), SC: O(26^2) -- 732/732 TCs Passed.\n        sort(a.begin(), a.end());\n        vector<vector<int>> dp(26, vector<int>(26, -1));\n        return memo(a, k, 0, a.size()-1, dp);\n    }\n\nprivate:\n    // SOL-3: DP -- MEMOIZATION -- TOP DOWN DP -- TC: O(26^2), SC: O(26^2) -- 732/732 TCs Passed.\n    int memo(vector<int> &a, const int &k, int i, int j, vector<vector<int>>&dp)\n    {\n        if ( i >= j )\n            return 0;\n        \n        if ( a[i] == 0 )\n            return dp[i][j] = memo(a, k, i+1, j, dp);\n        \n        if ( a[j] - a[i] <= k )\n            return dp[i][j] = 0;\n        \n        if ( dp[i][j] != -1 )\n            return dp[i][j];\n\n        int ans1 = a[i] + memo(a, k, i+1, j, dp);\n        int ans2 = a[j] - a[i] - k + memo(a, k, i, j-1, dp);\n        return dp[i][j] = min(ans1, ans2);\n    }\n    \n    // SOL-2: dfs/rec -- TC: O(2^26) -> O(10^7), SC: O(26) -- 732/732 TCs Passed.\n    int dfs(vector<int> &a, const int &k, int i, int j)\n    {\n        if ( i >= j )\n            return 0;\n        \n        if ( a[i] == 0 )\n            return dfs(a, k, i+1, j);\n        \n        if ( a[j] - a[i] <= k )\n            return 0;\n        \n        int ans1 = a[i] + dfs(a, k, i+1, j);\n        int ans2 = a[j] - a[i] - k + dfs(a, k, i, j-1);\n        return min(ans1, ans2);\n    }\n\n    // SOL-1: GREEDY -- WA -- 688 / 732 TCs passed -- 93.98%\n    int greedy(vector<int> &a, const int &k)\n    {\n        int ans = 0;\n        while ( true )\n        {\n            int mn = INT_MAX, mx = INT_MIN, mxi = 0, mni = 0;\n            for ( int i=0; i<26; i++ ) {\n                if ( a[i] != 0 ) {\n                    //mn = min(mn, a[i]);\n                    if ( a[i] <= mn ) {\n                        mn = a[i]; mni = i;\n                    }\n                    //mx = max(mx, a[i]);\n                    if ( a[i] >= mx ) {\n                        mx = a[i]; mxi = i;\n                    }\n                }\n            }\n\n            if ( mn == INT_MAX || mx == INT_MIN )\n                break;\n\n            int diff = mx-mn;\n            if ( diff <= k )\n                break;\n            else {\n                if ( diff - k < mn ) {\n                    ans += diff-k;\n                    a[mxi] -= (diff-k);\n                } else {\n                    ans += mn;\n                    a[mni] = 0;\n                }\n            } \n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Greedy', 'Depth-First Search', 'Recursion', 'Memoization', 'C']