LeetCode 3106 - Lexicographically Smallest String After Operations With Constraint

This problem asks us to transform a given string s into another string t such that the total transformation cost does not exceed k. Among all possible valid strings, we must return the lexicographically smallest one. The key detail is how the transformation cost is defined.

leetcodemediumstringgreedy

LeetCode Problem 3106

Difficulty: 🟡 Medium
Topics: String, Greedy

Solution

LeetCode 3106 - Lexicographically Smallest String After Operations With Constraint

Problem Understanding

This problem asks us to transform a given string s into another string t such that the total transformation cost does not exceed k. Among all possible valid strings, we must return the lexicographically smallest one.

The key detail is how the transformation cost is defined. Each character can be changed into any other lowercase English letter, and the cost of changing one character to another is the minimum cyclic distance on the alphabet circle.

The alphabet is considered cyclic:

a -> b -> c -> ... -> z -> a

For example:

  • The distance between 'a' and 'b' is 1
  • The distance between 'a' and 'z' is also 1
  • The distance between 'c' and 'x' is 5, because moving backward through the cycle is shorter

The total distance between two strings is the sum of the per-character distances.

The goal is not merely to minimize the total distance. Instead, we want the lexicographically smallest resulting string while staying within the allowed budget k.

Lexicographical order works exactly like dictionary order. Earlier characters are much more important than later characters. For example:

"aaaz" < "aaba"

because the strings first differ at index 2, where 'a' < 'b'.

This observation is extremely important because it means we should spend as much of the budget as possible making earlier characters smaller.

The constraints are relatively small:

  • 1 <= s.length <= 100
  • 0 <= k <= 2000

A length of only 100 means even somewhat expensive solutions could work. However, the problem has a clean greedy solution that runs in linear time.

Several edge cases are important:

  • If k = 0, we cannot modify anything
  • Characters near 'a' may wrap around through 'z'
  • Sometimes we cannot fully convert a character to 'a', so we must choose the smallest reachable character instead
  • Spending too much budget on later characters can prevent us from improving earlier characters, which would produce a non-optimal lexicographical result

Approaches

Brute Force Approach

A brute-force solution would attempt to generate all possible strings reachable within distance k, then select the lexicographically smallest one.

For each character, there are 26 possible choices. For a string of length n, that gives:

26^n

possible candidate strings.

For every candidate string, we would compute the total cyclic distance from the original string and keep only valid candidates.

This approach is correct because it examines every possible answer. However, it is computationally infeasible even for small inputs. With n = 100, the search space becomes astronomically large.

Optimal Greedy Approach

The crucial insight is that lexicographical order is dominated by earlier positions.

Suppose we are deciding how to modify character s[i]. Any improvement at index i is more valuable than any improvements at indices after i.

Therefore, at each position, we should make the character as small as possible using the remaining budget.

The smallest possible character is 'a'. So for every character:

  1. Compute the minimum cyclic cost to turn it into 'a'
  2. If we can afford that cost, convert it completely to 'a'
  3. Otherwise, use the remaining budget to move the character as far toward 'a' as possible

Because each position is optimized before moving to the next one, the resulting string is globally lexicographically minimal.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(26^n * n) O(26^n) Enumerates all possible transformed strings
Optimal Greedy O(n) O(n) Greedily minimizes each character from left to right

Algorithm Walkthrough

  1. Convert the string into a mutable array of characters.

Strings are immutable in many languages, so using an array or slice allows efficient modifications. 2. Process characters from left to right.

Earlier characters contribute more to lexicographical order, so we always prioritize them first. 3. For the current character, compute the minimum cyclic distance to 'a'.

If the current character is c, then:

  • Forward distance:
c - 'a'
  • Wrap-around distance:
26 - (c - 'a')

The true minimum cost is the smaller of these two values. 4. If the remaining budget k is large enough to convert the character fully to 'a', do it.

This produces the smallest possible character at the current position. 5. Otherwise, partially decrease the character using the remaining budget.

Since we cannot reach 'a', we should still make the character as small as possible.

Moving backward in the alphabet reduces lexicographical value directly. 6. Reduce k by the amount spent. 7. Continue until all characters are processed or k becomes 0. 8. Convert the character array back into a string and return it.

Why it works

The greedy strategy works because lexicographical comparison always prioritizes earlier positions. Any reduction at index i is more valuable than all possible reductions at indices greater than i.

Therefore, making each character as small as possible before moving to the next position guarantees the globally lexicographically smallest valid string.

Python Solution

class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        characters = list(s)

        for index in range(len(characters)):
            if k == 0:
                break

            current_char = characters[index]
            distance_to_a = min(
                ord(current_char) - ord('a'),
                26 - (ord(current_char) - ord('a'))
            )

            if distance_to_a <= k:
                characters[index] = 'a'
                k -= distance_to_a
            else:
                characters[index] = chr(ord(current_char) - k)
                k = 0

        return "".join(characters)

The implementation begins by converting the input string into a list of characters so individual positions can be modified efficiently.

The loop processes characters from left to right because lexicographical order depends most heavily on earlier positions.

For every character, the code computes the minimum cyclic distance required to transform it into 'a'. This uses both the direct backward movement and the wrap-around movement through 'z'.

If the remaining budget is sufficient, the character becomes 'a', and the used cost is deducted from k.

Otherwise, the algorithm spends the remaining budget decreasing the character as much as possible. Since the remaining budget is insufficient to reach 'a', partially reducing the character still produces the smallest achievable character at that position.

Finally, the modified list is joined back into a string.

Go Solution

func getSmallestString(s string, k int) string {
	characters := []byte(s)

	for i := 0; i < len(characters); i++ {
		if k == 0 {
			break
		}

		current := characters[i]

		distanceToA := min(
			int(current-'a'),
			26-int(current-'a'),
		)

		if distanceToA <= k {
			characters[i] = 'a'
			k -= distanceToA
		} else {
			characters[i] = current - byte(k)
			k = 0
		}
	}

	return string(characters)
}

func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows the same greedy logic as the Python version.

Since Go strings are immutable, the string is converted into a []byte slice before modification.

Character arithmetic is done directly using ASCII values. The expression:

current - 'a'

computes the alphabetical offset.

The helper min function is necessary because Go does not provide a built-in integer minimum function.

No overflow concerns exist because all operations remain within the lowercase English alphabet range.

Worked Examples

Example 1

Input:

s = "zbbz"
k = 3

Initial state:

Index Character Cost to 'a' Remaining k Action Result
0 z 1 3 convert to a abbz
1 b 1 2 convert to a aabz
2 b 1 1 convert to a aaaz
3 z 1 0 stop aaaz

Final answer:

"aaaz"

Example 2

Input:

s = "xaxcd"
k = 4

Initial state:

Index Character Cost to 'a' Remaining k Action Result
0 x 3 4 convert to a aaxcd
1 a 0 1 keep a aaxcd
2 x 3 1 partial decrease aawcd

At index 2, we only have 1 operation left, so:

x -> w

Final answer:

"aawcd"

Example 3

Input:

s = "lol"
k = 0

Since no operations are allowed, the algorithm immediately returns the original string.

Final answer:

"lol"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed exactly once
Space O(n) Mutable character array stores the result

The algorithm performs a single pass through the string. Every iteration uses only constant-time arithmetic and comparisons.

The additional space comes from converting the immutable string into a mutable character array or byte slice.

Test Cases

class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        characters = list(s)

        for index in range(len(characters)):
            if k == 0:
                break

            current_char = characters[index]
            distance_to_a = min(
                ord(current_char) - ord('a'),
                26 - (ord(current_char) - ord('a'))
            )

            if distance_to_a <= k:
                characters[index] = 'a'
                k -= distance_to_a
            else:
                characters[index] = chr(ord(current_char) - k)
                k = 0

        return "".join(characters)

solution = Solution()

assert solution.getSmallestString("zbbz", 3) == "aaaz"  # provided example
assert solution.getSmallestString("xaxcd", 4) == "aawcd"  # provided example
assert solution.getSmallestString("lol", 0) == "lol"  # zero budget
assert solution.getSmallestString("a", 0) == "a"  # single character unchanged
assert solution.getSmallestString("z", 1) == "a"  # wrap-around conversion
assert solution.getSmallestString("c", 2) == "a"  # exact cost conversion
assert solution.getSmallestString("d", 2) == "b"  # partial reduction
assert solution.getSmallestString("abc", 100) == "aaa"  # excess budget
assert solution.getSmallestString("zzz", 3) == "aaa"  # repeated wrap-around
assert solution.getSmallestString("bcd", 1) == "acd"  # prioritize earliest character

Test Summary

Test Why
"zbbz", 3 Validates multiple full conversions
"xaxcd", 4 Validates partial conversion
"lol", 0 Ensures zero budget works correctly
"a", 0 Smallest possible unchanged input
"z", 1 Tests cyclic wrap-around
"c", 2 Tests exact conversion cost
"d", 2 Tests incomplete reduction
"abc", 100 Tests very large budget
"zzz", 3 Tests repeated wrap-around conversions
"bcd", 1 Verifies greedy lexicographical prioritization

Edge Cases

One important edge case occurs when k = 0. In this situation, no modifications are allowed. A buggy implementation might still attempt transformations or perform invalid arithmetic. This implementation handles the case naturally because the loop exits immediately once it sees that k is zero.

Another important case involves cyclic wrap-around. Characters such as 'z' are actually very close to 'a' because the alphabet is circular. A naive implementation using only direct alphabetical distance would incorrectly think the cost from 'z' to 'a' is 25 instead of 1. The implementation correctly computes both directions and uses the smaller value.

A third edge case occurs when the remaining budget is insufficient to fully transform a character into 'a'. In that situation, we still want the smallest possible character at the current position. The implementation spends the remaining budget entirely on decreasing the current character, ensuring the lexicographically smallest achievable prefix.

Another subtle case is when the budget is larger than necessary. The algorithm does not try to spend all operations unnecessarily. Once all characters become 'a', additional budget has no effect, and the already minimal string is returned correctly.