111
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\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\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport java.util.*;\n\nclass Solution {\n\n    // to bump even indexes: shift, then bump\n\n    // 1 <= a <= 9 so: max meaningful bumps < 10 for ODD ids\n    // to make it for EVEN ids: 2*9 = 18 max bumps\n    // max meaningful bumps: 9\n\n    // max meaningful rotations: N - 1\n\n    // IDEA: try all possible bumps and rotations!!!\n\n    // a = 1: 0 -> 1,2,3,4,5,6,7,8,9\n    // a = 2: 0 -> 2,4,6,8\n    // a = 3: 0 -> 3,6,9\n\n    // NOTICE: bumping and rotating are SEPARATE!!! rotating only affects\n    // bumping in 1 way: if b is ODD, it allows us to also bump EVEN indexes\n    // so 2 ways to bump!!! even and odd indexes separately!!!\n    // Once we finish all possible bumping, we try all possible rotations!!!\n\n    // 1..maxB for ODD * 1...maxB for EVEN\n    // all possible rotations every time\n    public String findLexSmallestString(String s, int a, int b) {\n        this.smallest = s;\n        this.n = s.length();\n        this.a = a;\n        this.b = b;\n        int bumpEvenMax = b % 2 == 0 ? 0 : 9; // even B, can\'t bump even!!!\n\n        for (int bumpOddTimes = 0; bumpOddTimes <= 9; bumpOddTimes++) { // bump 0..9 times\n            for (int bumpEvenTimes = 0; bumpEvenTimes <= bumpEvenMax; bumpEvenTimes++) { // bump 0..9 times\n                StringBuilder sb = new StringBuilder(s);\n                bump(sb, 1, bumpOddTimes);\n                bump(sb, 0, bumpEvenTimes);\n\n                update(sb.toString());\n                rotate(sb.toString()); // try all possible rotations\n            }\n        }\n        return smallest;\n    }\n\n    void bump(StringBuilder sb, int startId, int times) {\n        if (times == 0) return;\n        for (int i = startId; i < n; i += 2) { // EVEN/ODD = startId\n            int cId = sb.charAt(i) - \'0\';\n            cId += a * times;\n            cId = cId % 10;\n            sb.setCharAt(i, (char) (cId + \'0\'));\n        }\n    }\n\n    void rotate(String s) {\n        for (int i = 0; i < n; i++) { // try all possible rotating\n            int endId = n - b;\n            s = s.substring(endId) + s.substring(0, endId);\n            update(s);\n        }\n    }\n\n\n    String smallest;\n    int n, a, b;\n\n    void update(String s) {\n        int diff = smallest.compareTo(s);\n        if (diff > 0) {\n            smallest = s;\n        }\n    }\n\n}\n\n\n```
['Java']