✅ My Well Commented C++ Solution || Beats 100% C++ of users || Easy to Understand
Intuition\nWhen I first encountered this problem, I thought of weather to go to the right side of the current character or left side. and then to know weather t
# Intuition\nWhen I first encountered this problem, I thought of weather to go to the right side of the current character or left side. and then to know weather to perform which operation for each character, based on the low cost to perform that operation on every character.\n\n# Approach \nI iterated through each character of the string from left to right. For each character, I calculated the cost of adding \'a\' (`add`) and the cost of subtracting from the current character (`subtract`). Then, I chose the operation with the lowest cost that didn\'t exceed the remaining cost `k`. I applied the operation if it was necessary. Finally, I returned the modified string.\n\n1. **Iterating through each character**: The algorithm starts by iterating through each character of the input string `s` from left to right. This allows us to process each character individually and make decisions based on its properties.\n\n2. **Calculating costs**: For each character, we calculate two costs:\n   - **add**: The cost of shifting the current character to the right in the alphabet to make it lexicographically smaller. This is calculated as the absolute difference between the ASCII value of \'z\' and the ASCII value of the current character plus 1. For example, if the current character is \'c\', then the cost of making it to \'a\' would be 23, because we need to go from \'c\' to \'z\' and then to \'a\'.\n   - **subtract**: The cost of shifting the current character to the left in the alphabet to make it lexicographically smaller. This is calculated as the minimum of the absolute difference between the ASCII value of the current character and the ASCII value of \'a\', and the remaining available cost `k`. This ensures that we don\'t exceed the available cost. For example, if the current character is \'c\' and the remaining cost `k` is 10, but it only takes a cost of 2 to go from \'c\' to \'a\', then we would choose 2 as the cost of subtraction.\n\n\n3. **Choosing the lowest cost operation**: Once we have calculated the costs, we choose the operation with the lowest cost that doesn\'t exceed the remaining cost `k`. We prioritize adding \'a\' if it has a lower cost, or subtracting from the current character if it has a lower cost and doesn\'t exceed `k`.\n\n4. **Applying the chosen operation**: After choosing the operation, we apply it if necessary. If we chose to add \'a\', we subtract the corresponding cost from `k` and modify the current character accordingly. If we chose to subtract from the current character, we also modify the character and subtract the corresponding cost from `k`.\n\n5. **Returning the modified string**: Finally, after processing all characters, we return the modified string `s`.\n\nThis approach ensures that we minimize the overall cost while transforming the input string into the smallest lexicographically string under the given constraints.\n\n\n# Complexity \n- Time complexity: $$O(n)$$, where $$n$$ is the length of the input string.\n- Space complexity: $$O(1)$$, as I used only a constant amount of extra space.\n\n# Code\n```\nclass Solution {\npublic:\n    string getSmallestString(string s, int k) {\n        int n = s.size();\n\n        // Start from left and replace characters based on the lowest cost\n        for (int i = 0; i < n; ++i) {\n            // If the current character is \'a\', no need to change\n            if(s[i]==\'a\'){\n                continue;\n            }\n            int add = abs(\'z\' - s[i] + 1); // Cost of addition\n            int subtract = min(abs(s[i] - \'a\'),k); // Cost of subtraction\n\n            // Choose the lowest cost operation\n            if ((add < subtract || add == subtract && add <= k) && add <= k) {\n                s[i] = char(s[i]-26+add); // Change the character\n                k -= add;\n            } \n            else if (subtract < add && subtract <= k) {\n                s[i] = char(s[i]-subtract); // Change the character\n                k -= subtract;\n            }\n        }\n        return s;\n    }\n};\n\n```
['C++']