O(n^2) complexity - Time and Memory beat 98%:  A solution way better than DFS.
Intuition\n Describe your first thoughts on how to solve this problem. \n\nIt is all about Math.\n\n1. figure out which index can be at index 0 with b as the ro
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nIt is all about Math.\n\n1. figure out which index can be at index 0 with b as the rotation number.\n2. figure out for every index, with a as the add value, what is the minimum value it can be. (look at the bestyoucando funtion)\n3. for every possible index 0 option from step 1, get the minumum value from step 2, merge odd and even substrings, and compare to find the minimum.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n^2)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def rotate(self, array, i):\n        return array[i:] + array[0:i]\n\n    def merge(self, arr1, arr2):\n        res = [0] * (len(arr1) + len(arr2))\n        for i in range(len(arr1)):\n            res[i * 2] = arr1[i]\n        for i in range(len(arr2)):\n            res[i * 2 + 1] = arr2[i]\n        return \'\'.join(res)\n\n    def bestyoucando(self, array, a):\n        res = {}\n        for i in range(len(array)):\n            if a in [1,3,7,9]:\n                addon = 10 - int(array[i])    \n            elif a in [0,2,4,6,8]:\n                addon = 10 + int(array[i]) % 2 - int(array[i])\n            else:\n                addon = 0 if int(array[i]) < 5 else 5\n            res[i] = \'\'.join(self.rotate([str((int(v)+addon)%10) for v in array], i))\n        return res\n\n    def findLexSmallestString(self, s: str, a: int, b: int) -> str:\n        posstart = [0]\n        c = b\n        n = len(s)\n        while c % n != 0:\n            posstart.append(n - c%n)\n            c += b\n        even = s[::2]\n        odd = s[1::2]\n        odd_add = self.bestyoucando(odd, a)\n        if b % 2 == 0:\n            even_add = {i:self.rotate(even, i) for i in range(len(even))}\n        else:\n            even_add = self.bestyoucando(even, a)\n \n        res = None\n        for sp in posstart:\n            if sp % 2 == 1:\n                cur = self.merge(odd_add[int(sp/2)], even_add[int((sp+1)/2) % len(even)])\n            else:\n                cur = self.merge(even_add[int(sp/2)], odd_add[int((sp+1)/2) % len(odd)])\n\n            if res is None:\n                res = cur\n            else:\n                if int(res) > int(cur):\n                    res = cur\n        return res\n        \n```
['Python3']