Java | C++ | Greedy Approach | Distance of Characters | T(N)= O(N*26)
Intuition\nFor each character in string we try all letters from \'a\' to \'z\', selecting the first one as which has less or equal distance to k\n\n# Approach\n
# Intuition\nFor each character in string we try all letters from \'a\' to \'z\', selecting the first one as which has less or equal distance to k\n\n# Approach\n### Distance Function (distance(char s1, char s2))\n\nThis function calculates the distance between two characters `s1` and `s2`. It considers the characters as arranged in a circle, where \'a\' and \'z\' are neighbors.\n\nHere\'s how it works:\n\n1. **Absolute Difference:** It calculates the absolute difference between the ASCII codes of the characters using `Math.abs(s1 - s2)`.\n\n2. **Circular Adjustment:** Since the alphabet is circular, it considers the minimum distance. It achieves this by finding the minimum of:\n   - The absolute difference (`diff`) calculated in step 1.\n   - The difference between 26 (number of letters in the alphabet) and the absolute difference (`26 - diff`).\n\nThis ensures that characters near the beginning and end of the alphabet (like \'a\' and \'z\') have a distance of 1 when considering the circular nature.\n\n**Example:**\n\n- `distance(\'a\', \'z\')`:\n  - Absolute difference: `Math.abs(\'a\' - \'z\')` = 25\n  - Circular adjustment: `min(25, 26 - 25)` = 1 (distance is 1 considering the circle)\n### getSmallestString(String s, int k) Function\n\nThis function finds the lexicographically smallest string `t` that can be obtained from the input string `s` by changing at most `k` characters. It considers a distance between characters when making these changes.\n\nHere\'s a breakdown of the steps involved:\n\n**1. Conversion to Character Array:**\n  - `char[] result = s.toCharArray();`: This line converts the input string `s` into a character array named `result`. This array will hold the modified string.\n\n**2. Iterating Through Characters:**\n  - The function uses an outer `for` loop to iterate through each character `i` in the original string `s`.\n\n**3. Finding the Best Replacement Character:**\n  - An inner `for` loop iterates through all lowercase letters (`char c = \'a\'; c <= \'z\'; c++`).\n  - Inside the inner loop:\n    - `distance(s.charAt(i), c)`: This calculates the distance between the current character `s[i]` and the candidate replacement character `c` using a separate `distance` function (assumed to be defined elsewhere).\n    - `if (distance(s.charAt(i), c) <= k)`: This checks if changing the current character to `c` is allowed within the `k` limit based on the distance.\n      - If the distance is less than or equal to `k`:\n        - `result[i] = c;`: The character in the `result` array at position `i` is updated with the new character `c`.\n        - `k -= distance(s.charAt(i), c);`: The remaining allowed changes (`k`) are decremented by the distance used for this replacement.\n        - `break;`: The inner loop exits as a suitable replacement has been found within the limit.\n\n**4. Returning the Modified String:**\n  - `return new String(result);`: This line converts the modified character array `result` back into a String object and returns it.\n\n\n## Example: s = "zbbz", k = 3\n\nLet\'s walk through how the code works for the input string `s = "zbbz"` and `k = 3` allowed changes:\n\n**1. Initialization:**\n\n- The input string `s` is converted to a character array: `result = [\'z\', \'b\', \'b\', \'z\']`.\n- The number of allowed changes `k` is set to 3.\n\n**2. Iterating Through Characters:**\n\n**Iteration 1: i = 0 (Character \'z\')**\n\n- The inner loop iterates through all lowercase letters (`c = \'a\'; c <= \'z\'; c++`).\n- `c = \'a\'`: The distance between \'z\' and \'a\' is 1, which is less than `\'k\'=3`.\n- so `result[i]` is updated to \'a\'.\n- `k` is decremented becomes 2.\n- we exit this loop\n\n\n**Iteration 2: i = 1 (Character \'b\')**\n\n- The inner loop iterates through characters.\n- `distance(\'b\', \'a\')` is 1 (within `k`), so `result[i]` is updated to \'a\'.\n- `k` is decremented becomes `1`.\n- we exit this loop\n\n**Iteration 3: i = 2 (Character \'b\')**\n\n- Similar to iteration 2, `\'b\'` is changed to `\'a\'` (distance 1), and `k` becomes `0`.\n\n**Iteration 4: i = 3 (Character \'z\')**\n\n- no change is made to `\'z\'` as `k` becomes `0`we do not find distance equal to `0`.\n\n**3. Returning the Result:**\n\n- The final modified character array is `[\'a\', \'a\', \'a\', \'z\']`.\n- It\'s converted back to a string: `"aaaz"`.\n\nTherefore, the output for `s = "zbbz", k = 3` is `"aaaz"`.\n## Complexity\n\n### Time Complexity\n\nThe time complexity of the code depends on the nested loops:\n\n* **Outer loop:** Iterates `n` times, once for each character in the input string `s`.\n* **Inner loop:** Iterates through all lowercase letters (26 characters) in the worst case.\n\n## In the worst case, the inner loop runs completely for every character in the outer loop (if all characters need to be replaced). This leads to a total of `n * 26` iterations.\n\nHowever, in some cases, the inner loop might exit early if a suitable replacement is found within the allowed `k` changes. This reduces the total number of iterations.\n\nTherefore, the time complexity is considered **O(n * k)** in the worst case.\n\n### Space Complexity\n\nThe space complexity of the provided code is dominated by the character array `result` used to store the modified string.\n\n* The size of `result` is directly proportional to the input string length `n`.\n* In the worst case, all characters in the string might be changed, so `result` will hold `n` characters.\n\nTherefore, the space complexity is considered **O(n)**.\n\n# Code\n```java []\nclass Solution {\n    public int distance(char s1, char s2) {\n        int diff = Math.abs(s1 - s2);\n        return Math.min(diff, 26 - diff);\n    }\n    public String getSmallestString(String s, int k) {\n        char[] result = s.toCharArray();\n        for (int i = 0; i < s.length(); i++) {\n            for (char c = \'a\'; c <= \'z\'; c++) {\n                if (distance(s.charAt(i), c) <= k) {\n                    result[i] = c;\n                    k -= distance(s.charAt(i), c);\n                    break;\n                }\n            }\n        }\n        return new String(result);\n        \n    }\n}\n```
['String', 'Greedy', 'C++', 'Java']