Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The two operations can interact: rotation changes which digits occupy odd positions, so choosing each operation greedily can miss a smaller reachable string. Treat each full string as a graph state and each allowed operation as an edge, then explore every reachable state once.

Approach

Begin a breadth-first search with the original string in both the queue and visited set. For each state, update the smallest string seen and construct two neighbors: add a modulo ten at every odd index, and rotate right by b positions. Enqueue each unseen neighbor. Return the smallest state after the queue empties. Visited-state tracking prevents cycles from repeated additions or rotations; BFS is used for exhaustive reachability, not to minimize the number of operations.

class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        n = len(s)
        q = deque([s])
        seen = set()
        seen.add(s)
        res = s

        while q:
            curr = q.popleft()
            res = min(res, curr)

            o1 = list(curr)
            for i in range(1, n, 2):
                o1[i] = str((int(o1[i]) + a) % 10)
            o1 = "".join(o1)
            if not o1 in seen:
                seen.add(o1)
                q.append(o1)

            o2 = list(curr)
            o2 = o2[-b:] + o2[:-b]
            o2 = "".join(o2)
            if not o2 in seen:
                seen.add(o2)
                q.append(o2)

        return res

Complexity analysis

Let n = s.length and V be the number of reachable strings (V <= 100n under the problem constraints). Time: O(Vn) to build and compare both neighbors of every state. Auxiliary space: O(Vn) for the visited strings and BFS queue.