JAVA MOST OPTIMAL SOLUTION || BEATS 100 % Users || Do UpVote
Let\'s first Understand the Problem Statement first : \n\nSince the problem states that find the samllest possible String. \n\n1.Let\'s Understand By an Example
# Let\'s first Understand the Problem Statement first : \n\n**Since the problem states that find the samllest possible String.** \n\n**1.Let\'s Understand By an Example what is the smallest String :** \nSuppose we have Two Strings s1 and s2\ns1 = "xawb"\ns2 = "yawb" \n\nsmallest = s1\nHere Both the Strings are similar but s1 has the differentiator character(x) and s2 has(y) and accoring to the alphabets x appears before y hence the s1 string is smaller. \n\n2.In this problem we are given a String and a k Integer which states that : We are at most allowed to flip a character by the most k value\nonce we fliped a character reduce the value of k.\n\n# NOTE: The Distance between the two characters can be in cyclic direction for example the distance between (a , c) = 2  , (a , d) = 3 , (z , a) = 1 because of cycle a will appear after z . (x , a) = 3\n\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n**The Intuition is explained in 4 steps : **\n1. My Most priority character will be \'a\' because as it is the most smallest characters\n\n2. If I am standing on a character char(i) then look in both the directions left and right calculate the distance between the char(i) to char \'a\' and choose the minimum distance.\n\n3. If the minimum distance is lesser or Equal to K then make that character as \'a\' and reduce the k value by k - minDistanceToCharacterA\n\n4. If the minimumDistance is > k then we cannot replace the current character to \'a\'. In this case choose the most smallest character which is in range of k for eg: String : "upvote"  and k = 2 in this case we cannot change the char(0) to \'a\' hence the smallest character of the u are (a-t) and k = 2 hence u will become as (\'u\' - k) = (\'u\' - 2) == s  . Final String = \'spvote\' \n# Approach\n<!-- Describe your approach to solving the problem. -->\nIterate on the String and do all the checks written in Intuition Steps . If didn\'t understand then please read the 4 steps again.\n\n# Complexity\n- Time complexity:\n-  O(N) since atmost we will iterate on the entire given String.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n.\n\n- Space complexity:\n- O(1) because we are not using any extra space for solving the answer . Since Function is expected to return a String . O(N) ans String is used to store the final Answer.\n- Overall Space Complexity : O(1);\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nclass Solution {\n    public String getSmallestString(String s, int k) {\n        \n        StringBuilder ans = new StringBuilder();\n        int n = s.length();\n\n        for(int i = 0 ; i < n ; i++){\n            //Check smallest Distance to reach \'a\'\n            int leftDist = (\'z\' - s.charAt(i)) + 1; //LeftDirection\n            int rightDist = (s.charAt(i) - \'a\'); //RightDirection Formula\n\n            int finalDist = Math.min(leftDist , rightDist);\n\n            //Check whether distance to reach a is <= k \n            if(k >= finalDist){ //Possible\n                ans.append(\'a\');\n                k -= finalDist;\n            }else{ //Not Possible to reach \'a\'\n                char ch = (char) (s.charAt(i) - k);\n                ans.append(ch);\n                //add the remaining Substring to answer and break\n                if(i+1 < n){\n                    ans.append(s.substring(i+1));\n                }\n                break;\n            }\n        }\n        return ans.toString();\n    }\n}\n```
['Java']