Lexicographically Smallest String After Operations With Constraint - Solution & Explanation

Problem Overview: You are given a lowercase string s and an integer k. Each operation can shift a character forward or backward in the alphabet with wrap-around (cyclic). The goal is to produce the lexicographically smallest possible string while keeping the total shift cost ≤ k.

Approach 1: Greedy Approach Using Character Replacement (O(n) time, O(1) space)

The key observation is that lexicographic order is determined from left to right. Reducing earlier characters has a much bigger impact than modifying later ones. Iterate through the string and try to convert each character to 'a'. Compute the cyclic distance between the current character and 'a'. If the required cost is ≤ k, convert the character directly to 'a' and subtract that cost from k. If the cost is larger than the remaining budget, reduce the character by exactly k steps toward 'a' and stop further reductions since the budget becomes zero.

This works because any extra reduction on later characters cannot produce a lexicographically smaller result than minimizing earlier characters first. The algorithm performs a single pass through the string and constant-time arithmetic per character, giving O(n) time and O(1) space.

Approach 2: Cyclic Distance and Replacement Strategy (O(n) time, O(1) space)

This approach explicitly models the alphabet as a cycle of size 26. For each character, compute the minimal cyclic distance to 'a' using min(c - 'a', 26 - (c - 'a')). If this minimal distance is within the remaining operation budget, replace the character with 'a'. Otherwise, partially move the character toward 'a' by exactly k positions in the backward direction and terminate since the budget is exhausted.

The cyclic distance calculation is important for cases like 'z', where wrapping forward by one step reaches 'a'. By always selecting the smallest cyclic move that minimizes the character value, the algorithm guarantees the smallest possible prefix at every step. The logic relies on simple arithmetic rather than simulation, which keeps the solution linear.

This problem mainly combines ideas from string manipulation and greedy algorithms. The greedy choice is safe because reducing earlier characters always dominates improvements later in the string.

Recommended for interviews: The greedy single-pass solution is what interviewers expect. A brute-force exploration of possible shifts would be exponential and unnecessary. Showing the greedy reasoning—minimizing each character from left to right while tracking the remaining budget—demonstrates strong understanding of lexicographic ordering and greedy optimization.