Lexicographically Smallest String After Applying Operations - Solution & Explanation

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.