C++ O(n ^ 2)
This one is such a grim problem... I felt it\'s the most complicated problem in the contest.\n\n> I am wondering if O(n) could be possible, e.g. with Booth\'s a
This one is such a grim problem... I felt it\'s the most complicated problem in the contest.\n\n> I am wondering if O(n) could be possible, e.g. with Booth\'s algorithm. \n\nIf `b` is even, we only can modify digits in the even positions (odd will remain odd after the shift). So, we need to inspect up to `10` variations of our string, each shifted up to `n` times, where `n` is the size of the string. For each shift, we compare up to `n` elements.\n\nIf `b` is odd, we need to check up to `100` variations: 10 odd * 10 even, each shifted up to `n` times.\n\nFor the complexity analysis, both `10` and `100`are constant, leaving us with checking up to `n` rotations - O(n ^ 2).\n\n```cpp\nbool less(string &s, int i, int j) {\n    for (auto k = 0; k < s.size(); ++k) {\n        if (s[(k + i) % s.size()] != s[(k + j) % s.size()])\n            return s[(k + i) % s.size()] < s[(k + j) % s.size()];\n    }\n    return false;\n}\nstring findLexSmallestString(string s, int a, int b) {\n    string res = s;\n    bool odd[10] = {};\n    while (odd[s[0] - \'0\'] == false) {\n        odd[s[0] - \'0\'] = true;\n        bool even[10] = {};\n        while (even[s[1] - \'0\'] == false) {\n            even[s[1] - \'0\'] = true;\n            int best_r = 0;\n            vector<bool> rotate(s.size());\n            for (int r = b; !rotate[r]; r = (r + b) % s.size()) {\n                rotate[r] = true;\n                if (less(s, r, best_r))\n                    best_r = r;\n            }\n            res = min(res, s.substr(best_r) + s.substr(0, best_r));                \n            for (int k = 1; k < s.size(); k += 2)\n                s[k] = \'0\' + (s[k] - \'0\' + a) % 10;\n        }\n        if (b % 2) {\n            for (int k = 0; k < s.size(); k += 2)\n                s[k] = \'0\' + (s[k] - \'0\' + a) % 10;\n        }\n    }\n    return res;\n}\n```
[]