C++ 100% Faster | String Matching | Easy Step By Step Solution
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem asks us to minimize the distance between a string s and another strin
![Zombie Upvote.png](https://assets.leetcode.com/users/images/ad2fa6e7-cbc1-4021-a2ec-1594833ae789_1712461140.3444526.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem asks us to minimize the distance between a string s and another string t through character changes. We can achieve this by iterating through s and analyzing the distance between each character and its lexicographically smallest neighbor (\'a\').\n\n- Here\'s the key insight:\n    - If the distance between a character s[i] and \'a\' is less than or equal to the available operations (k), we can directly change s[i] to \'a\'. This minimizes the distance for that character.\n    - If the distance is greater than k, we can still make some changes. We need to find the new character for s[i] that utilizes the remaining operations (k) most effectively. We can either move s[i] closer to \'a\' (if possible) or move it as far away from \'z\' (the character with the maximum distance from \'a\').\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Iterate through the string:**\n    - For each character s[i], calculate its distance to \'a\':\n       - dist = min(s[i] - \'a\', \'z\' - s[i] + 1). This considers both clockwise and counter-clockwise rotations in the cyclic order of characters.\n2. **Change characters based on distance and available operations:**\n    - If dist <= k:\n      - Change s[i] to \'a\'. This minimizes the distance for this character and consumes dist operations.\n      - Decrement k by dist to reflect the used operations.\n    - If dist > k and k > 0:\n      - If moving s[i] closer to \'a\' is possible (i.e., s[i] - k >= \'a\'), decrement s[i] by k.\n      - Otherwise, move s[i] as far away from \'z\' as possible using the remaining operations. Set s[i] to \'z\' - (k - 1).\n      - In both cases, set k to 0 as all remaining operations are used.\n3. **Return the modified string:**\n    - After iterating through the entire string, return the modified s.\n\n# Complexity\n- Time complexity: **O(n)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(1)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#pragma GCC optimize("03", "unroll-loops")\nclass Solution {\npublic:\n    string getSmallestString(string s, int k) {\n        for (int i = 0; i < s.size(); ++i) {\n            int dist = min(s[i] - \'a\', \'z\' - s[i] + 1);\n            if(k >= dist){\n                k -= dist;\n                s[i] = \'a\';\n            }else{\n                if(k > 0){\n                    if(s[i] - k >= \'a\'){\n                        s[i]-=k;\n                    }else{\n                        s[i] = \'z\' - (k - 1);\n                    }\n                    k=0;\n                }\n                break;\n            }\n        }\n        return s;\n    }\n};\nauto init = [](){\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```
['String', 'C++']