Lexicographically Smallest String After Applying Operations: BFS State Exploration

You are given a string s of even length consisting only of digits, an integer a, and an integer b. You can apply two operations any number of times in any order:

1. Add a to all odd-indexed digits of s (0-indexed). Digits cycle modulo 10.
2. Rotate s to the right by b positions.

Return the lexicographically smallest string you can obtain by applying these operations.

This is LeetCode 1625: Lexicographically Smallest String After Applying Operations, and it is a great problem for learning BFS-based state-space exploration. The operations create a finite set of reachable strings, and BFS lets you visit every one of them efficiently.

Why this problem matters

Many interview problems boil down to searching a state space. You have a starting state, a set of operations that transform it, and you need to find the optimal result. This problem makes that structure explicit: the "states" are strings, the "edges" are add and rotate, and the "goal" is the lexicographic minimum.

Once you recognize this as a graph traversal problem, the solution follows naturally. The same BFS-over-states technique applies to problems like "Open the Lock" (LeetCode 752), "Sliding Puzzle" (LeetCode 773), and any problem where you explore transformations to find an optimum.

The approach

The key insight is that the set of reachable strings is finite. The string has a fixed length, each character is a digit (0 to 9), and both operations are deterministic. That means the total number of distinct strings you can reach is bounded, and eventually you will revisit a state you have already seen.

This naturally maps to BFS:

1. Start with the original string in a queue and a visited set.
2. For each string in the queue, apply both operations (add and rotate) to produce two new strings.
3. If a new string has not been visited, add it to the queue and the visited set.
4. Track the lexicographic minimum across all visited strings.
5. When the queue is empty, return the minimum.

The add operation modifies only odd-indexed digits, adding a modulo 10. The rotate operation shifts the string right by b, wrapping the last b characters to the front. Both are simple to implement.

from collections import deque

def find_lex_smallest_string(s: str, a: int, b: int) -> str:
    visited = set()
    visited.add(s)
    queue = deque([s])
    best = s

    while queue:
        curr = queue.popleft()
        if curr < best:
            best = curr

        added = list(curr)
        for i in range(1, len(added), 2):
            added[i] = str((int(added[i]) + a) % 10)
        added = "".join(added)

        rotated = curr[-b:] + curr[:-b]

        for nxt in [added, rotated]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append(nxt)

    return best

Step-by-step walkthrough

The BFS starts from the original string and fans out. Each string in the queue produces two children: one from adding a to odd indices, one from rotating right by b. The visited set prevents reprocessing. Since there are at most 10^(n/2) * n possible states (bounded by digit values and rotation positions), the search always terminates.

Notice that the add operation only affects odd-indexed positions, and it cycles through at most 10 values per digit. The rotate operation cycles through at most n distinct rotations. Together, these create a manageable state space even for strings of moderate length.

Complexity analysis

Here, S is the total number of distinct reachable strings and N is the length of the string. For each state, we do O(N) work to apply the add and rotate operations and to compare strings. S is bounded by the product of possible digit combinations and rotation positions. In the worst case, S can be large, but the constraints of this problem (string length up to 100) keep it practical.

Space is O(S) for the visited set and the queue. Each entry is a string of length N.

Edge cases to watch for

• a = 0: The add operation does nothing. You can only rotate, so you try all n / gcd(n, b) distinct rotations and pick the smallest.
• b is even: When b is even, rotating an even-length string by an even amount means the add operation always hits the same set of indices (odd positions stay odd). This limits the states but the BFS handles it correctly.
• b is odd: An odd rotation can shift odd-indexed positions to even indices and vice versa. This means the add operation can eventually reach all digits, not just the original odd-indexed ones. The BFS naturally explores this expanded space.
• All digits identical: Every add and rotate produces the same string. The BFS terminates immediately.
• a = 5: The digits at odd indices cycle through only two values (e.g., 0 and 5, or 3 and 8). This reduces the number of reachable states.

The building blocks

BFS state-space exploration

The core pattern here is treating strings as nodes in a graph and operations as edges. You start from one node, apply all possible transformations, track visited nodes, and search for the optimum.

visited = set()
visited.add(start)
queue = deque([start])
best = start

while queue:
    state = queue.popleft()
    if state < best:
        best = state
    for next_state in generate_next_states(state):
        if next_state not in visited:
            visited.add(next_state)
            queue.append(next_state)

This template works for any problem where you need to find the best reachable state through a finite set of transformations. The same structure appears in "Open the Lock," "Word Ladder," and "Sliding Puzzle." The only thing that changes is the generate_next_states function.

String rotation

Right-rotating a string by b positions is a single-line operation: s[-b:] + s[:-b]. This takes the last b characters and moves them to the front. It is the same technique used in "Rotate String" and "Rotate Array," just applied to a string. Understanding this slice pattern is valuable because rotation shows up in many string and array problems.

From understanding to recall

You have seen how BFS explores the state space of string transformations. The algorithm is direct: queue up states, apply operations, skip visited strings, track the minimum. The code is short and the logic is clean.

The tricky part under interview pressure is recognizing that this is a BFS problem in the first place. The problem says "apply operations any number of times in any order," which is a signal that you are searching over a state space. Once you see that signal, the BFS template writes itself.

Spaced repetition helps you internalize both the recognition step and the implementation. You practice identifying "state-space search" problems from their descriptions, and you practice writing the BFS loop with a visited set from memory. After a few rounds, you see "apply operations to find optimal result" and immediately reach for BFS.

Related posts

• Rotting Oranges - Multi-source BFS on a grid, the same queue-based exploration pattern in a different setting
• Clone Graph - BFS traversal over a graph structure, using a visited map to avoid cycles
• Number of Islands - BFS flood fill on a grid, another application of state-space search

CodeBricks breaks this problem into its BFS state-exploration building block, then drills it with spaced repetition. You type the queue loop, the visited set, and the state generation from scratch until the pattern is automatic. When an interview problem asks you to "find the best result after applying operations," you do not hesitate. You write BFS.