1625

class Solution {
public:
    string findLexSmallestString(string s, int a, int b){
        set<string> st;
        queue<string> q;
        string minstring = s;
        q.push(s);
        st.insert(s);
        while(!q.empty()) {
            string cur = q.front(); q.pop();
            minstring = min(cur, minstring);
            string added  = add(cur,a);
            string rotated = rotate(cur,b);
            if(st.find(added) == st.end())
                q.push(added), st.insert(added);
            if(st.find(rotated) == st.end())
                q.push(rotated), st.insert(rotated);
        }
        return minstring;
    }

    string add(string s, int x) {
        for (int i=1; i<s.size(); i += 2){
            char &c = s[i];
            c = '0' + (c-'0'+x)%10;
        }
        return s;
    }

    string rotate(string s, int x){
        reverse(s.begin(), s.end());
        reverse(s.begin(), s.begin()+x);
        reverse(s.begin()+x, s.end());
        return s;
    }
};