Skip to main content
Talentd

Lexicographically Smallest String After Operations With Constraint - Solution & Explanation

MediumStringGreedy16 min readAsked at: ServiceNow
Practice this problem

Problem Statement

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.

Approach Overview

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.

Approach 1: Greedy Approach Using Character Replacement

In this approach, we aim to replace characters in the given string by rotating towards 'a', as it is the lexicographically smallest character. For each character in the string 's', calculate the minimum distance to 'a' using the cyclic nature of the alphabet. If the distance is within the allowed limit 'k', make the change and reduce 'k' accordingly. The goal is to make the string lexicographically smaller by changing as many characters as possible to 'a'.

The program checks each character to see how far it is from 'a'. If the distance is within 'k', it changes the character to 'a' and reduces 'k'. If the character cannot be changed to 'a' without exceeding 'k', it shifts the character backwards within the limit.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), as the operation is performed in-place.

Try this approach in the editor →

Approach 2: Cyclic Distance and Replacement Strategy

This alternative approach focuses on leveraging the cyclic nature of the alphabet, considering direct backward shifts within the allowed 'k'. It aims to achieve 'a' replacements as secondary, while possibly transforming non-contiguous characters where allowed for optimal string formation.

The C solution examines character shifts, favoring whole changes to 'a' if possible, otherwise backwards within 'x-a in order to fully utilize 'k'. Early termination occurs if contrary adjustments would exhaust the budget.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), iterating over the string length. Space Complexity: O(1), made entirely in-place.

Try this approach in the editor →

Approach 3: Enumeration

We can traverse each position of the string s. For each position, we enumerate all characters less than the current character, calculate the cost d to change to this character. If d leq k, we change the current character to this character, subtract d from k, end the enumeration, and continue to the next position.

After the traversal, we get a string that meets the conditions.

The time complexity is O(n times |\Sigma|), and the space complexity is O(n). Here, n is the length of the string s, and |\Sigma| is the size of the character set. In this problem, |\Sigma| leq 26.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach Using Character Replacement

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), as the operation is performed in-place.

Cyclic Distance and Replacement Strategy

Time Complexity: O(n), iterating over the string length. Space Complexity: O(1), made entirely in-place.

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Character ReplacementO(n)O(1)Best general solution. Minimizes characters from left to right using remaining operation budget.
Cyclic Distance StrategyO(n)O(1)Useful when reasoning about alphabet wrap-around and minimal cyclic shifts.

Video Solution

3106. Lexicographically Smallest String After Operations With Constraint | Adhoc | Strings • Aryan Mittal • 4,437 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Lexicographically Smallest String After Operations With Constraint easy or hard?
The problem is rated Medium because the greedy strategy is not immediately obvious. Once you recognize that minimizing earlier characters always improves lexicographic order, the implementation becomes straightforward with a single pass and simple arithmetic.
Lexicographically Smallest String After Operations With Constraint Python/Java solution
Most implementations follow the same greedy logic across languages. Convert the string to a mutable array, iterate from left to right, compute the minimal cyclic distance to 'a', update the character if the budget allows, and decrease k accordingly. This approach works in Python, Java, C++, C#, and JavaScript with identical O(n) complexity.
How to solve Lexicographically Smallest String After Operations With Constraint in O(n)?
Iterate through the string from left to right. For each character, compute the cyclic distance to 'a'. If that distance is less than or equal to k, convert the character to 'a' and subtract the cost from k. Otherwise decrease the character by k positions toward 'a' and stop since the operation budget becomes zero.
What is the best approach for Lexicographically Smallest String After Operations With Constraint?
The optimal approach is a greedy left-to-right traversal. For each character, compute the minimal cyclic distance to 'a'. If the cost is within the remaining k budget, convert the character to 'a'; otherwise reduce it as much as possible using the remaining operations. This produces the smallest possible prefix at every step and runs in O(n) time with O(1) space.
Is Lexicographically Smallest String After Operations With Constraint asked at Google/Amazon/Meta?
Greedy string transformation problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. The problem tests understanding of lexicographic ordering, greedy decision making, and efficient string manipulation under constraints.
What data structure is used in Lexicographically Smallest String After Operations With Constraint?
The problem mainly uses basic string manipulation and arithmetic operations on characters. No advanced data structures are required. The solution relies on greedy traversal and cyclic distance calculations within the alphabet.
What is the time complexity of Lexicographically Smallest String After Operations With Constraint?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed exactly once and only constant-time arithmetic operations are performed. Space complexity is O(1) because the algorithm modifies characters directly without extra data structures.

Ready to solve this problem?

Practice Lexicographically Smallest String After Operations With Constraint with our built-in code editor and test cases.

Practice on FleetCode
Previous

Lexicographically Smallest String After Substring Operation