# Lexicographically Smallest String After Operations With Constraint
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/lexicographically-smallest-string-after-operations-with-constraint)
Canonical: https://scaleengineer.com/dsa/problems/lexicographically-smallest-string-after-operations-with-constraint
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [ServiceNow](https://scaleengineer.com/companies/servicenow)
---
## Problem
You are given a string `s` and an integer `k`.

Define a function `distance(s1, s2)` between two strings `s1` and `s2` of the same length `n` as:

* The **sum** of the **minimum distance** between `s1[i]` and `s2[i]` when the characters from `'a'` to `'z'` are placed in a **cyclic** order, for all `i` in the range `[0, n - 1]`.

For example, `distance("ab", "cd") == 4`, and `distance("a", "z") == 1`.

You can **change** any letter of `s` to **any** other lowercase English letter, **any** number of times.

Return a string denoting the **lexicographically smallest** string `t` you can get after some changes, such that `distance(s, t) <= k`.

**Example 1:**

**Input:** s = "zbbz", k = 3

**Output:** "aaaz"

**Explanation:**

Change `s` to `"aaaz"`. The distance between `"zbbz"` and `"aaaz"` is equal to `k = 3`.

**Example 2:**

**Input:** s = "xaxcd", k = 4

**Output:** "aawcd"

**Explanation:**

The distance between "xaxcd" and "aawcd" is equal to k = 4.

**Example 3:**

**Input:** s = "lol", k = 0

**Output:** "lol"

**Explanation:**

It's impossible to change any character as `k = 0`.

**Constraints:**

* `1 <= s.length <= 100`
* `0 <= k <= 2000`
* `s` consists only of lowercase English letters.

# Approaches
## Dynamic Programming with Memoization
A less efficient but valid approach is to use dynamic programming with memoization. This method systematically explores all possible transformations to find the lexicographically smallest one. We define a recursive function that, for each position in the string, tries every possible character change and recursively solves for the rest of the string. Memoization is used to store the results for subproblems to avoid redundant computations.
**Time:** O(n² * k * C), where n is the length of the string, k is the initial budget, and C is the alphabet size (26). The state space is O(n * k). For each state, we iterate through C characters, and string operations (concatenation and comparison) take up to O(n) time. · **Space:** O(n² * k) to store the memoized suffix strings. Each of the O(n * k) states can store a string of length up to n.
**Pros:** Guarantees finding the optimal solution by exhaustively exploring the valid search space.; Provides a structured, albeit inefficient, way to think about the problem.
**Cons:** Extremely high time and space complexity, making it infeasible for the given constraints.; Repeated string manipulations (concatenation, comparison) are very slow.
### Explanation
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)`.

```java
class Solution {
    private String s;
    private String[][] memo;

    public String smallestString(String s, int k) {
        this.s = s;
        if (k == 0) return s;
        this.memo = new String[s.length()][k + 1];
        return solve(0, k);
    }

    private String solve(int index, int remainingK) {
        if (index == s.length()) {
            return "";
        }
        if (memo[index][remainingK] != null) {
            return memo[index][remainingK];
        }

        String bestResult = null;

        for (char c = 'a'; c <= 'z'; c++) {
            int cost = distance(s.charAt(index), c);
            if (remainingK >= cost) {
                String suffix = solve(index + 1, remainingK - cost);
                String currentResult = c + suffix;
                if (bestResult == null || currentResult.compareTo(bestResult) < 0) {
                    bestResult = currentResult;
                }
            }
        }
        return memo[index][remainingK] = bestResult;
    }

    private int distance(char c1, char c2) {
        int diff = Math.abs(c1 - c2);
        return Math.min(diff, 26 - diff);
    }
}
```
### Algorithm
- 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)`.

## Greedy Approach
The most efficient way to solve this problem is with a greedy approach. Since we want the lexicographically smallest string, we should process the string from left to right and make each character as small as possible. For each character, we attempt to change it to 'a', the smallest possible character. If we have enough budget `k`, we perform this change and update our budget. If not, we use all of our remaining budget to make the current character as small as we can, which exhausts the budget for any further changes.
**Time:** O(n), where n is the length of the string. We perform a single pass through the string. · **Space:** O(n) to store the character array for the result string. This is because strings are immutable in Java. If modifying the input string were allowed, space complexity would be O(1).
**Pros:** Highly efficient with linear time complexity.; Simple and straightforward to implement.; Optimal for the given problem constraints.
**Cons:** The correctness of the greedy choice might require some reasoning to be fully convinced, although it is intuitive for this problem.
### Explanation
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.

```java
class Solution {
    public String smallestString(String s, int k) {
        if (k == 0) {
            return s;
        }
        char[] resultChars = s.toCharArray();
        for (int i = 0; i < resultChars.length; i++) {
            if (k == 0) {
                break;
            }
            char originalChar = resultChars[i];
            // The distance to 'a' is the value of the character minus 'a'
            // or 26 minus that value, whichever is smaller.
            int distToA = Math.min(originalChar - 'a', 26 - (originalChar - 'a'));

            if (distToA <= k) {
                resultChars[i] = 'a';
                k -= distToA;
            } else {
                // If we can't reach 'a', use all remaining k to get as close as possible.
                // The smallest character is achieved by subtracting from the current one.
                resultChars[i] = (char) (originalChar - k);
                k = 0;
            }
        }
        return new String(resultChars);
    }
}
```
### Algorithm
- 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.

# Solutions
### Java

```java
class Solution {
public
  String getSmallestString(String s, int k) {
    char[] cs = s.toCharArray();
    for (int i = 0; i < cs.length; ++i) {
      char c1 = cs[i];
      for (char c2 = 'a'; c2 < c1; ++c2) {
        int d = Math.min(c1 - c2, 26 - c1 + c2);
        if (d <= k) {
          cs[i] = c2;
          k -= d;
          break;
        }
      }
    }
    return new String(cs);
  }
}

```

### CPP

```cpp
class Solution {
public:
  string getSmallestString(string s, int k) {
    for (int i = 0; i < s.size(); ++i) {
      char c1 = s[i];
      for (char c2 = 'a'; c2 < c1; ++c2) {
        int d = min(c1 - c2, 26 - c1 + c2);
        if (d <= k) {
          s[i] = c2;
          k -= d;
          break;
        }
      }
    }
    return s;
  }
};

```

### Python

```python
class Solution:
    def getSmallestString(self, s: str, k: int) -> str: cs = list(s) for i, c1 in enumerate(s): for c2 in ascii_lowercase: if c2 >= c1: break d = min(ord(c1) - ord(c2), 26 - ord(c1) + ord(c2)) if d <= k: cs[i] = c2 k -= d break return "" . join(cs)

```