【No brute force】O(N^2 / GCD(b, N)) time, O(N) space
Note: in the title N = s.length.\n\n# First Thought\n---\nWe need efficiently to answer these two questions:\n How many times to rotate the string?\n How many t
Note: in the title `N = s.length`.\n\n# **First Thought**\n---\nWe need efficiently to answer these two questions:\n* How many times to rotate the string?\n* How many times of `a` to add on for each rotation position?\n\n# **TL; DR**\n---\nIn short, we need to rotate the string for only `s.length / gcd(b, s.length)` times.\n\nFor each rotation position, there are only two possible ways to add `a` to possibly get the minimum:\n* If `b` is even, then only numbers at odd indices (0-based) can be modified by adding a multiple of `a`\n* If `b` is odd, then numbers at odd indicies can be modified by adding a multiple of `a`, and the numbers at even indicies can also be modified by adding a multiple of `a`.\n\nTo determine the multiple of `a`, we only need to look at how to minimize the number at index 0 and 1.\n\nIf the above explanation makes sense to you, you can jump to the code at the end. Otherwise, let me explain in details:\n\n# **How many times to rotate the string?**\n---\nIt is obvious that rotating the string for `s.length` times will cover all possible rotation positionos. But is it necessary? It is possible that **sometimes we don\'t have to rotate that many times**. For example, when `b == s.length`, there is only one rotation position. Rotating the string `s` for any arbitrary times won\'t actually change `s`. How to get the minimum number of times needed to rotate?\n\nTo simulate the rotation, image you repeat the string `s` infinite times and get an infinite long string `S = sssssssss......`. And you have a pointer initially pointing at the head of `S`. The pointer each time moves right by `b` steps (this is corresponding to rotating the string by `b`). The next time when the pointer points to the head of certain `s` (let\'s denote it as `S[i]`), we know we would see the same pattern of moves if we continue to move rightwards. **This is exactly the point we do not need to rotate the string further**.\n\nWe know `i` is a multiple of `b`, because we move the pointer by `b` steps each time. We also know it is a multiple of `s.length` because it is the head of certain `s`. So `i` is the Least Common Multiple (LCM) of `b` and `s.length`. At this point, **how many times have we moved the pointer? `i / b` times!**\n\nSo the minimum required times of rotations is\n```\n  i / b\n= LCM(b, s.length) / b\n= (b * s.length / GCD(b, s.length)) / b\n= s.length / GCD(b, s.length)\n```\n\n\n# **Which numbers can be modified?**\n---\nNote that `s.length % 2 == 0`.\n\nIf `b` is even, even if you rotate the string later, it will still **always and only the numbers that currently at the odd indices that can be modified**. You will never be able to modify those even-indices number\n\nIf `b` is odd, then the if you rotate the string by `b`, the current odd-indexed numbers will go to even indices, and vice versa. You will have the chance to modify the numbers that are currently at even indices. Then you can rotate the string a few times to let it come back to the origional rotation position. So **when `b % 2 == 1`, you can add odd-index numbers all by a multiple of `a`, and add all even-index numbers by another (can be equal) multiple of `a`**.\n\n\n# **For each given rotation position, how to determine the lexicographically smallest?**\n---\n\nWhen `b` is even, we want to minimize the number at `s[1]`. That let us know what multiple of `a` do we want to add on all the odd-index numbers.\n\nWhen `b` is odd, we want to minimize both the numers at `s[0]` and `s[1]`. That let us know what multiple of `a` to add on all the odd-index numbers, and what to add on all the even-index numbers.\n\nSo **we do not have to try all 10 possible multiples of `a`**.\n\n# **Python Code**\n---\nhttps://github.com/kaiwensun/leetcode/blob/master/1501-2000/1625.Lexicographically%20Smallest%20String%20After%20Applying%20Operations.py\n\n```\nfrom fractions import gcd\nclass Solution(object):\n    def findLexSmallestString(self, s, a, b):\n\n        def get_smallest_head(head, a):\n            if a == 5:\n                return min(head, (head + 5) % 10)\n            return 0 if a % 2 else head % 2\n            \n        def add_a(lst, diff_odd, diff_even):\n            for i in xrange(1, len(lst), 2):\n                lst[i] += diff_odd\n                lst[i] %= 10\n            if diff_even:\n                for i in xrange(0, len(lst), 2):\n                    lst[i] += diff_even\n                    lst[i] %= 10\n            return lst\n            \n        res = list(map(int, s))\n        cur = list(map(int, s))\n        rotate_times = len(s) // gcd(b, len(s))\n        for _ in xrange(rotate_times):\n            diff_odd = get_smallest_head(cur[1], a) - cur[1]\n            diff_even = b % 2 and get_smallest_head(cur[0], a) - cur[0]\n            if res > add_a(cur, diff_odd, diff_even):\n                res = list(cur)\n            cur = cur[b:] + cur[:b]\n        return "".join(map(str, res))\n```\n\n# **Complexity**\n---\n## Time complexity:\n```\n  T \n= (times of rotations) * T(reconstruct the smallest string at the rotation position)\n= (LCM(b, s.length) / b) * s.length\n= s.length ^ 2 / GCD(b, s.length)\n```\n## Space complexity: \n`O(s.length)` for the space of `cur` and `res`.\n
[]