1. Failed DP,  2. Greedy
\n\n\n# Using dynamic programming - Gave me memory limit exceeding\n# \n\n\nclass Solution {\n\t//O(n * k)\n    public String getSmallestString(int n, int k) {\
![image](https://assets.leetcode.com/users/images/4bcaacfb-8182-492c-a7ac-b30318949413_1647920423.2616134.png)\n\n\n# Using dynamic programming - Gave me memory limit exceeding\n# ![image](https://assets.leetcode.com/users/images/5efebbec-384a-4429-ad58-417261dbf7ff_1647920476.4489262.png)\n\n```\nclass Solution {\n\t//O(n * k)\n    public String getSmallestString(int n, int k) {\n        String dp[][] = new String[n + 1][k + 1];\n        \n        return smallestString(n, k, dp);\n    }\n    \n\t//O(l * sum)\n    String smallestString(int l, int sum, String dp[][]) {\n        if (l == 0 && sum == 0) {\n            return "";\n        }\n        \n        if (l == 0 || sum < 0) {\n            return "-1";\n        }\n        \n        if (dp[l][sum] != null) {\n            return dp[l][sum];\n        }\n        \n\t\t//O(26)\n        for (int i = 0; i < 26; i++) {\n            String str = smallestString(l - 1, sum - i - 1, dp);\n            if (str.equals("-1")) {\n                continue;\n            }\n            \n            return dp[l][sum] = (char) (\'a\' + i) +str;\n        }\n        \n        return dp[l][sum] = "-1";\n    }\n}\n```\n![image](https://assets.leetcode.com/users/images/1a81cbf7-45df-43a5-bf32-84f7e75d4cdf_1647920660.588031.png)\n![image](https://assets.leetcode.com/users/images/de9958cb-d274-4343-8098-4d635033fa40_1647920735.2207842.png)\n\nConstraints are higher hence gives MLE.\n\n# Using greedy approach.\n![image](https://assets.leetcode.com/users/images/4093e8cb-b96b-41b6-a316-3b71f2658e34_1647921162.1465936.png)\n```\nclass Solution {\n    public String getSmallestString(int n, int k) {\n        \n        StringBuilder sb = new StringBuilder();\n        \n\t\t//O(N)\n        while (n > 0 && k > 0) {\n            int ind = 0;\n            //find appropriate character - O(26)\n            while ((n - 1) * 26 < k - ind -1 && ind < 26) {\n                ind++;\n            }\n            \n            sb.append((char) (\'a\' + ind));//append it to string\n            k -= (ind + 1); // update k\n            n--; // update length\n        }\n        \n        return sb.toString();\n    }\n}\n```\n\nTC : O(N)\nSC : O(N)\n\n\n\n\n
['Dynamic Programming', 'Greedy']