[Proof] Group Theory | Java 14ms 100% | Optimal O(N^2) time, O(N) space
The idea is simply to find all possibilities and compare them one by one. However, the difficulty of tracking all possibilities is that (1) and (2) operations o
The idea is simply to find all possibilities and compare them one by one. However, the difficulty of tracking all possibilities is that (1) and (2) operations occur randomly, so we want to group the same operations together to fix their order, and hence easily loop over the number of each kind of operations.\n\nOperations:\n(1) Add `a` to all *odd* indices of `s` (0-indexed, even length).\n(2) Rotate `s` to the right by `b` positions.\n\nAny possibility can be written as a composition of (1) and/or (2). For example, say `s = "1234"`, `a = 3`, `b = 1`. Then (1)(1) is `"1830"`, (2)(1)(2) is `"6442"`, etc., and `s` itself is just 0 time of either operation.\n\nFirstly, please note that both (1) and (2) are cyclic. That is, doing 10 times of (1) goes back to the original `s`; and so is doing `s.length` times of (2).\n\nMathematically, (1) and (2) form a group. In fact, the periods can be further optimized by considering the order of (1) and (2):\n|(1)| = 10 / gcd(10, a), and\n|(2)| = s.length / gcd(s.length, b).\n\n-----\n\n**If `b` is even**, then the two operations are commutative (abelian), i.e. (1)(2) = (2)(1).\n\nWe move all (2) to the end, so every possibility can be written as (1)...(1)(2)...(2).\n\nTherefore, we are able to loop the number of (1) then loop the number of (2), to iterate all possibilities.\n\nTime complexity: O(|(1)|\\*|(2)|) \\* O(`s.length`) \u2264 O(10\\*`s.length`^2).\nThe second term O(`s.length`) is the cost of comparison.\n\n-----\n\n**If `b` is odd**, (1)(2) \u2260 (2)(1). We introduce a helper operation:\n\n(3) Add `a` to all *even* indices of `s`.\n\n(3) is already in the group because (3) = (2)^(-1)\xB7(1)\xB7(2), where (2)^(-1) denotes the inverse of (2). With transposition, we have (2)(1) = (3)(2) and (2)(3) = (1)(2). Besides, note that (1) and (3) are commutative, i.e. (1)(3) = (3)(1), and |(3)| = |(1)| as well.\n\nSuch being the case, any possibility can be expressed as (1)...(1)(3)...(3)(2)...(2).\n\nLikewise, we nest 3 loops to iterate all possibilities.\n\nTime complexity: O(|(1)|\\*|(3)|\\*|(2)|) \\* O(`s.length`) \u2264 O(100\\*`s.length`^2).\n\n-----\n\n##### Java Solution\n\nSpace complexity: O(s.length)\n\n```\nclass Solution {\n    public String findLexSmallestString(String s, int a, int b) {\n        String ans = s;\n        int aCycle = 10 / gcd(10, a);\n        int bCycle = s.length() / gcd(s.length(), b);\n        \n        String curS = s;\n        if (b % 2 == 0) {  // b is even\n            for (int i = 1; i <= aCycle; i++) {\n                curS = oddAddA(curS, a);\n                for (int j = 1; j <= bCycle; j++) {\n                    curS = rotateB(curS, b);\n                    if (curS.compareTo(ans) < 0) {\n                        ans = curS;\n                    }\n                }\n            }\n        } else {  // b is odd\n            for (int i = 1; i <= aCycle; i++) {\n                curS = oddAddA(curS, a);\n                for (int k = 1; k <= aCycle; k++) {\n                    curS = evenAddA(curS, a);\n                    for (int j = 1; j <= bCycle; j++) {\n                        curS = rotateB(curS, b);\n                        if (curS.compareTo(ans) < 0) {\n                            ans = curS;\n                        }\n                    }\n                }\n            }\n        }\n        return ans;\n    }\n\t\n\t/** Operation (1) */\n    private String oddAddA(String s, int a) {\n        StringBuilder sb = new StringBuilder(s);\n        for (int i = 1; i < s.length(); i += 2) {\n            sb.replace(i, i + 1, Integer.toString((s.charAt(i) - \'0\' + a) % 10));\n        }\n        return sb.toString();\n    }\n\t\n\t/** Operation (3) */\n    private String evenAddA(String s, int a) {\n        StringBuilder sb = new StringBuilder(s);\n        for (int i = 0; i < s.length(); i += 2) {\n            sb.replace(i, i + 1, Integer.toString((s.charAt(i) - \'0\' + a) % 10));\n        }\n        return sb.toString();\n    }\n    \n\t/** Operation (2) */\n    private String rotateB(String s, int b) {\n        return s.substring(b, s.length()) + s.substring(0, b);\n    }\n\n    private int gcd(int x, int y) {\n        if (x % y == 0) {\n            return y;\n        } else {\n            return gcd(y, x % y);\n        }\n    }\n}\n```\n\n<img alt="Java Solution Submission Details" width=450 src=https://assets.leetcode.com/users/images/aabaa50a-2d58-4b4a-b7b5-687e2172cbe9_1603004066.405815.png>\n
[]