C++ BFS Solution with Explanations | R: 85.44%, M: 76.70%
Intuition\nTo solve the problem of finding the lexicographically smallest string after applying addition and rotation operations, I used an approach based on Br
# Intuition\nTo solve the problem of finding the lexicographically smallest string after applying addition and rotation operations, I used an approach based on Breadth-First Search (BFS).\n\n# Approach\n\nPlace the original string **s** in the **queue** and in **visited**. Start a loop while the queue is not empty: \n- Extract the current string and compare it with the current best result (result), update result if necessary. \n- Applying rotation: rotate the string by b positions and check if such a string has already been seen. If not, add it to the queue and visited. \n- Applying addition: add a to each digit at an odd position in the string and repeat the check, as with rotation. \n- Completion: Once the queue is emptied, return result as the lexicographically smallest string.\n\nIn this algorithm, it was initially decided to start with rotation to quickly generate different string configurations, and then apply addition to these configurations. This is because rotation is a more \'global\' operation in terms of changing the structure of the string, while addition is more \'local,\' altering specific characters.\n\nStarting with rotation can help explore the diversity of strings more quickly, as each rotation creates a new unique configuration for subsequent addition.\n\nBFS allows for systematic exploration of all possible strings. The use of unordered_set ensures that each unique string is considered only once, enhancing efficiency.\n\n# Complexity\n- Time complexity:\n$$O(n * 10 * 10)$$ where n is the length of the string (the maximum number of rotation and addition operations for each string). The *space complexity* also depends on the number of unique strings that can be generated.\n\n# Code\n```\nclass Solution {\npublic:\n    string rotateRight(const string& s, int b) {\n        int n = s.size();\n        return s.substr(n - b) + s.substr(0, n - b);\n    }\n\n    string findLexSmallestString(string s, int a, int b) {\n        unordered_set<string> visited;\n        queue<string> q;\n        q.push(s);\n        visited.insert(s);\n        string result = s;\n\n        while (!q.empty()) {\n            string current = q.front();\n            q.pop();\n            result = min(result, current);\n\n            // rotate\n            string rotated = rotateRight(current, b);\n            if (visited.find(rotated) == visited.end()) {\n                visited.insert(rotated);\n                q.push(rotated);\n            }\n\n            // add\n            for (int i = 1; i < s.size(); i += 2) {\n                current[i] = ((current[i] - \'0\') + a) % 10 + \'0\';\n            }\n\n            if (visited.find(current) == visited.end()) {\n                visited.insert(current);\n                q.push(current);\n            }\n        }\n\n        return result;\n    }\n};\n```
['Breadth-First Search', 'C++']