Lexicographically Smallest String After Applying Operations

Lexicographically Smallest String After Applying Operations

What is this problem about?

The "Lexicographically Smallest String After Applying Operations interview question" gives you two operations:

1. Add a constant a to all characters at odd indices (modulo 10).
2. Rotate the string to the right by b positions. You can apply these operations any number of times in any order. The goal is to find the lexicographically smallest string possible. This "Lexicographically Smallest String After Applying Operations coding problem" is a state-space exploration challenge.

Why is this asked in interviews?

This problem is asked at companies like Amazon to test a candidate's ability to use "Breadth-First Search interview pattern" or "Enumeration interview pattern". Since the number of possible strings is finite (though potentially large), it evaluates whether you can systematically visit all reachable states without getting stuck in an infinite loop.

Algorithmic pattern used

BFS is the ideal pattern here. You start with the initial string and treat each unique string generated as a node in a graph. Use a Queue for BFS and a Set to keep track of seen strings to avoid cycles. For each string you pull from the queue, apply both operations (add and rotate) and add the resulting new strings to the queue and the set. Keep track of the minimum string seen throughout the traversal.

Example explanation

String: "5525", a=9, b=2

1. Start: "5525". Min = "5525".
2. Add: "5(5+9)2(5+9)" -> "5424". Queue: ["5424"].
3. Rotate: "2555". Queue: ["5424", "2555"].
4. Continue until all reachable strings are processed. Eventually, you might find a string starting with "2" or "1" which would be the new minimum.

Common mistakes candidates make

• No "seen" set: Forgetting to track which strings have already been visited, leading to an infinite loop.
• Incorrect rotation logic: Confusing left rotation with right rotation or getting the slice indices wrong.
• Missing the full state space: Only trying one operation repeatedly instead of exploring all combinations.

Interview preparation tip

When you have a set of operations that can be repeated indefinitely, think of it as a Graph problem. The "lexicographically smallest" result is simply the "best" node found during a full traversal (BFS or DFS).