Problem Statement in English

You’re given a string s of even length consisting of digits from 0 to 9, and two integers a and b. You can apply either of the following two operations any number of times and in any order on s:

  1. Increment all odd-indexed digits by a (wrapping around from 9 to 0).
  2. Rotate the string to the right by b positions.

Your task is to find the lexicographically smallest string that can be obtained by applying these operations.

Approach

You just have to explore all possibile states.

Solution in Python


class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        seen = set()
        res = s
        sl = len(s)
        
        def f(state):
            nonlocal res
            if state in seen:
                return
            
            seen.add(state)
            
            res = min(res, state)
            
            l = [int(x) for x in state]
            for i in range(1, sl, 2):
                l[i] = (l[i] + a) % 10
            nstate = ''.join(str(x) for x in l)
            f(nstate)
            
            nstate = state[-b:] + state[:-b]
            f(nstate)
        
        f(s)
        return res

Complexity

  • Time: O(n∗m)O(n * m)
    Where n is the length of the string and m is the number of unique states.

  • Space: O(m)O(m)
    Since we are using recursion and that can have a stack height of m.

Mistakes I Made

Overcomplicated the implementation.

And we are done.