Skip to main content
Talentd

Lexicographically Smallest String After Applying Operations - Solution & Explanation

MediumStringDepth-First SearchBreadth-First SearchEnumeration19 min readAsked at: Amazon, Jpmorgan
Practice this problem

Problem Statement

You are given a string s of even length consisting of digits from 0 to 9, and two integers a and b.

You can apply either of the following two operations any number of times and in any order on s:

  • Add a to all odd indices of s (0-indexed). Digits post 9 are cycled back to 0. For example, if s = "3456" and a = 5, s becomes "3951".
  • Rotate s to the right by b positions. For example, if s = "3456" and b = 1, s becomes "6345".

Return the lexicographically smallest string you can obtain by applying the above operations any number of times on s.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example, "0158" is lexicographically smaller than "0190" because the first position they differ is at the third letter, and '5' comes before '9'.

 

Example 1:

Input: s = "5525", a = 9, b = 2
Output: "2050"
Explanation: We can apply the following operations:
Start:  "5525"
Rotate: "2555"
Add:    "2454"
Add:    "2353"
Rotate: "5323"
Add:    "5222"
Add:    "5121"
Rotate: "2151"
Add:    "2050"​​​​​
There is no way to obtain a string that is lexicographically smaller than "2050".

Example 2:

Input: s = "74", a = 5, b = 1
Output: "24"
Explanation: We can apply the following operations:
Start:  "74"
Rotate: "47"
​​​​​​​Add:    "42"
​​​​​​​Rotate: "24"​​​​​​​​​​​​
There is no way to obtain a string that is lexicographically smaller than "24".

Example 3:

Input: s = "0011", a = 4, b = 2
Output: "0011"
Explanation: There are no sequence of operations that will give us a lexicographically smaller string than "0011".

 

Constraints:

  • 2 <= s.length <= 100
  • s.length is even.
  • s consists of digits from 0 to 9 only.
  • 1 <= a <= 9
  • 1 <= b <= s.length - 1

Approach Overview

Problem Overview: You start with a numeric string s. Two operations are allowed: add a to every digit at odd indices (mod 10), or rotate the string to the right by b positions. Apply any sequence of operations and return the lexicographically smallest string you can produce.

Approach 1: Brute Force with BFS to Check All Combinations (Time: O(K * n), Space: O(K * n))

Model the problem as a state graph where each node is a string configuration. From a state, generate two neighbors: one after applying the add operation and one after the rotate operation. Use Breadth-First Search with a visited set to avoid revisiting the same string. While exploring states, keep track of the lexicographically smallest string encountered. If K is the number of reachable configurations, BFS processes each once and each operation costs O(n) for string transformation.

The key insight is that operations form cycles. Digits wrap around modulo 10 and rotations eventually repeat, so the reachable state space is finite. BFS guarantees you enumerate every valid configuration without duplicates. This approach is straightforward and reliable for typical constraints.

Approach 2: Mathematical Cycle Detection to Minimize Operations (Time: O(n * 10 * (n / gcd(n, b))), Space: O(1))

The operations follow predictable cycles. Rotating by b repeatedly only produces n / gcd(n, b) unique rotations. Similarly, repeatedly adding a to digits cycles every 10 operations because digits are modulo 10. Instead of exploring a graph, iterate through all possible rotation states and simulate addition cycles on odd indices (and even indices when rotation changes parity).

For each rotation, try all possible additions (at most 10) to minimize digits at odd positions. If rotation allows even positions to be affected, apply addition cycles there as well. Build the candidate string and track the smallest lexicographic result. This turns the search into controlled enumeration over small mathematical cycles instead of an unbounded traversal.

The logic relies on modular arithmetic properties of digit addition and rotation parity. You still explore all reachable outcomes, but without storing every intermediate state. The approach combines string manipulation with careful enumeration patterns often seen in DFS style state exploration problems.

Recommended for interviews: Start with the BFS state exploration. It clearly models the problem as a graph and demonstrates understanding of visited-state pruning. After that, discuss the mathematical cycle optimization. Interviewers often appreciate recognizing that rotations and digit additions repeat in predictable cycles, reducing the search space significantly.

Approach 1: Brute Force with BFS to Check All Combinations

This approach leverages a breadth-first search (BFS) to explore all possible string configurations by applying the given operations. We keep track of already-visited states to avoid processing them again, storing the lexicographically smallest string found in the process.

The key point is to simulate the effect of each operation (addition and rotation) and use a queue to handle the states and explore until no new configurations can be found.

The Python solution uses BFS to explore each possible configuration of the string obtained by performing the operations. Starting from the initial string, it performs an addition operation and a rotation operation, pushing these new strings to the queue to be evaluated later, ensuring that each configuration is only visited once by using a set.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n * 10 * n), where n is the length of the string, as the cycle for each index via addition is at most 10, and there are n possible configurations for rotations.

Space Complexity: O(n * n) for storing possible configurations in the 'visited' set.

Try this approach in the editor →

Approach 2: Mathematical Cycle Detection to Minimize Operations

This approach reduces complexity by detecting cycles in possible configurations without exhausting all possibilities. It leverages mathematical principles governing rotations and additions, where applying operationsform sequences and constraints that can terminate the search early once a smallest string is identified.

By identifying recurring patterns in transformation sequences, computational resources can be conserved, and optimizations applied, particularly in identifying redundant operations that do not lead to smaller strings.

This Python code reduces operations by recognizing cycles in resulting transformations the operations can achieve. It systematically applies a limited number of additions and explores all rotations, using combinations to ensure minimal complexity is faced.

Code

Python

Python

Complexity

Time Complexity: O(10 * n^2), reduced due to early detection of cycles and constraints on possibilities given operation properties.

Space Complexity: O(n).

Try this approach in the editor →

Approach 3: BFS

Since the data scale of this problem is relatively small, we can use BFS to brute-force search all possible states and then take the lexicographically smallest state.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Enumeration

We observe that for the addition operation, a digit will return to its original state after at most 10 additions; for the rotation operation, the string will also return to its original state after at most n rotations.

Therefore, the rotation operation produces at most n states. If the rotation count b is even, the addition operation only affects digits at odd indices, resulting in a total of n times 10 states; if the rotation count b is odd, the addition operation affects both odd and even index digits, resulting in a total of n times 10 times 10 states.

Thus, we can directly enumerate all possible string states and take the lexicographically smallest one.

The time complexity is O(n^2 times 10^2) and the space complexity is O(n), where n is the length of string s.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force with BFS to Check All Combinations

Time Complexity: O(n * 10 * n), where n is the length of the string, as the cycle for each index via addition is at most 10, and there are n possible configurations for rotations.

Space Complexity: O(n * n) for storing possible configurations in the 'visited' set.

Mathematical Cycle Detection to Minimize Operations

Time Complexity: O(10 * n^2), reduced due to early detection of cycles and constraints on possibilities given operation properties.

Space Complexity: O(n).

BFS—
Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force BFS State ExplorationO(K * n)O(K * n)General solution when modeling operations as a graph of states
Mathematical Cycle EnumerationO(n * 10 * (n / gcd(n,b)))O(1)When recognizing rotation and addition cycles to avoid full graph traversal

Video Solution

Leetcode 1625 | Lexicographically Smallest String After Applying Operations | Common Pattern | MIK • codestorywithMIK • 10,174 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Lexicographically Smallest String After Applying Operations easy or hard?
This problem is typically rated Medium difficulty. The challenge is recognizing that operations form cycles and avoiding infinite exploration. Once modeled as a finite state graph with BFS or cycle enumeration, the implementation becomes manageable.
Lexicographically Smallest String After Applying Operations Python/Java solution
Python and Java implementations usually follow the BFS state exploration strategy. Use a queue to process strings, generate the two possible next states, and track visited states with a set. The smallest lexicographic string encountered during traversal is returned as the final answer.
How to solve Lexicographically Smallest String After Applying Operations in O(n)?
A near-linear solution relies on cycle detection using modular arithmetic. Rotations repeat after n / gcd(n, b) steps and digit additions repeat every 10 operations due to modulo 10. Enumerating these cycles lets you test all valid configurations without storing every state explicitly.
What is the best approach for Lexicographically Smallest String After Applying Operations?
Breadth-First Search over string states is the most common approach. Treat each string as a node and generate neighbors by applying the add and rotate operations. Track visited states to avoid repetition and update the smallest lexicographic string during traversal. Time complexity is O(K * n) where K is the number of reachable configurations.
Is Lexicographically Smallest String After Applying Operations asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Amazon and Google because it combines string manipulation with state-space search. Interviewers often expect candidates to model operations as graph transitions and use BFS or reasoning about cycles.
What data structure is used in Lexicographically Smallest String After Applying Operations?
The BFS solution primarily uses a queue for traversal and a hash set to track visited strings. These structures prevent revisiting states and ensure each configuration is processed once. String manipulation is used to apply digit addition and rotation operations.
What is the time complexity of Lexicographically Smallest String After Applying Operations?
The BFS approach runs in O(K * n) time where K is the number of reachable string states and n is the string length. Each state requires O(n) time to apply the add or rotate operation. A mathematical cycle optimization reduces exploration to O(n * 10 * (n / gcd(n, b))).

Ready to solve this problem?

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

Practice on FleetCode
Previous

Lexicographically Smallest String After a Swap

Next

Lexicographically Smallest String After Substring Operation