Lexicographically Smallest String After Applying Operations

main.md

Question

Approach

I explore all reachable strings from s using BFS (or DFS) on the state space of strings, applying the two allowed operations until no new string appears. I keep a visited set to avoid cycles and always track the lexicographically smallest string seen. Since |s| ≤ 100 and every operation maps a string to another string of the same length with digits 0..9, the reachable state space is finite and BFS will terminate quickly in practice for the given constraints.

Implementation

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

        while dq:
            cur = dq.popleft()
            if cur < best:
                best = cur

            arr = list(cur)
            for i in range(1, n, 2):
                arr[i] = str((int(arr[i]) + a) % 10)
            op1 = ''.join(arr)
            if op1 not in seen:
                seen.add(op1)
                dq.append(op1)

            op2 = cur[-b:] + cur[:-b]
            if op2 not in seen:
                seen.add(op2)
                dq.append(op2)

        return best

Complexities

• Time: O(n)
• Space: O(n)