cpp concise solution (memoization)
intuition: on each step we either rotate or add a to the string then recompute the lowest string.\n\nSo let\'s do both independently and keep tracking the lowes
intuition: on each step we either rotate or add *a* to the string then recompute the lowest string.\n\nSo let\'s do both independently and keep tracking the lowest string. As you can see there are subproblems. so let\'s save it for later.\n```\nclass Solution {\npublic:\n    void dfs(string &s, string &small, int a, int b, unordered_map<string, string> &memo) {\n        if (memo.count(s)) return;\n        string res = s, str = res;\n        memo[s] = res;\n        rotate(str.begin(), str.begin() + b, str.end()); // rotate current string\n        dfs(str, small, a, b, memo);\n        if (memo[str] < res) res = memo[str];\n        \n        for (int i = 0; i < 9; i++) { // or add it\n            for (int j = 1; j < s.length(); j+=2)\n                s[j] = \'0\' + ((s[j] - \'0\') + a) % 10;\n            if (s < res) res = s;\n            dfs(s, small, a, b, memo);\n        }\n        if (small > res) small = res;\n        memo[s] = res;\n    }\n    string findLexSmallestString(string s, int a, int b) {\n        unordered_map<string, string> memo;\n        string res = s;\n        dfs(s, res, a, b, memo);\n        return  res;\n    }\n};\n```
['Memoization', 'C']