Lexicographically Smallest String After Operations With Constraint

• Create a memoization table memo[n+1][k+1] initialized to a null/sentinel value.
• Define a recursive function solve(i, k):
  • If i == n, return "".
  • If memo[i][k] is not null, return it.
  • Initialize best_result = null.
  • For each character c from 'a' to 'z':
    • Calculate cost = distance(s[i], c).
    • If k >= cost:
      • Recursively call recursive_suffix = solve(i + 1, k - cost).
      • Form candidate = c + recursive_suffix.
      • If best_result is null or candidate is lexicographically smaller than best_result, update best_result = candidate.
  • Store best_result in memo[i][k] and return it.
• The final answer is the result of the initial call solve(0, k).

The core idea is to build the solution from left to right, making the optimal choice at each position by exploring all possibilities. We define a function solve(i, k) which computes the lexicographically smallest suffix t[i:] given a remaining budget k. To compute solve(i, k), we try setting t[i] to every character c from 'a' to 'z'. For each choice c, we calculate the cost d = distance(s[i], c). If we have enough budget (k >= d), we recursively find the best suffix for the rest of the string: suffix = solve(i + 1, k - d). We then form a candidate result c + suffix and compare it with the best result found so far for the state (i, k). To avoid recomputing results for the same state (i, k), we use a 2D array for memoization. The final answer is the result of the initial call solve(0, initial_k).

1class Solution {2    private String s;3    private String[][] memo;4 5    public String smallestString(String s, int k) {6        this.s = s;7        if (k == 0) return s;8        this.memo = new String[s.length()][k + 1];9        return solve(0, k);10    }11 12    private String solve(int index, int remainingK) {13        if (index == s.length()) {14            return "";15        }16        if (memo[index][remainingK] != null) {17            return memo[index][remainingK];18        }19 20        String bestResult = null;21 22        for (char c = 'a'; c <= 'z'; c++) {23            int cost = distance(s.charAt(index), c);24            if (remainingK >= cost) {25                String suffix = solve(index + 1, remainingK - cost);26                String currentResult = c + suffix;27                if (bestResult == null || currentResult.compareTo(bestResult) < 0) {28                    bestResult = currentResult;29                }30            }31        }32        return memo[index][remainingK] = bestResult;33    }34 35    private int distance(char c1, char c2) {36        int diff = Math.abs(c1 - c2);37        return Math.min(diff, 26 - diff);38    }39}

• Convert the input string s into a character array, result_chars.
• Iterate from i = 0 to s.length() - 1:
  • If k == 0, break the loop.
  • Let c = result_chars[i].
  • Calculate dist_to_a = min(c - 'a', 26 - (c - 'a')).
  • If k >= dist_to_a:
    • Set result_chars[i] = 'a'.
    • Decrement k by dist_to_a.
  • Else:
    • We cannot reach 'a'. The smallest character we can reach is c - k.
    • Set result_chars[i] = (char)(c - k).
    • Set k = 0.
• Convert result_chars back to a string and return it.

The problem asks for the lexicographically smallest string. This property strongly suggests a greedy approach. To make a string as small as possible, we should try to make its characters as small as possible, starting from the leftmost character. We iterate through the input string s from left to right (index i = 0 to n-1). At each position i, we try to make the character t[i] as small as possible, which is 'a'. We calculate the cost to change s[i] to 'a'. The cyclic distance to 'a' from a character c is min(c - 'a', 26 - (c - 'a')). If our remaining budget k is sufficient to cover this cost, we make the change: set t[i] = 'a' and update k by subtracting the cost. If the budget is not sufficient, we cannot change s[i] to 'a'. To still get the lexicographically smallest character possible at this position, we must use our entire remaining budget k to move s[i] as close to 'a' as possible. This means changing s[i] to the character s[i] - k. After this operation, our budget k becomes 0. Since the budget is now exhausted, all subsequent characters of t must be the same as in s. The loop can terminate early once k becomes 0. This greedy strategy works because making a character at an earlier position smaller will never prevent us from making a character at a later position smaller, thus the local optimal choices lead to a global optimum.

1class Solution {2    public String smallestString(String s, int k) {3        if (k == 0) {4            return s;5        }6        char[] resultChars = s.toCharArray();7        for (int i = 0; i < resultChars.length; i++) {8            if (k == 0) {9                break;10            }11            char originalChar = resultChars[i];12            // The distance to 'a' is the value of the character minus 'a'13            // or 26 minus that value, whichever is smaller.14            int distToA = Math.min(originalChar - 'a', 26 - (originalChar - 'a'));15 16            if (distToA <= k) {17                resultChars[i] = 'a';18                k -= distToA;19            } else {20                // If we can't reach 'a', use all remaining k to get as close as possible.21                // The smallest character is achieved by subtracting from the current one.22                resultChars[i] = (char) (originalChar - k);23                k = 0;24            }25        }26        return new String(resultChars);27    }28}