Number following a pattern

Given a pattern containing only I’s and D’s. I for increasing and D for decreasing.
Devise an algorithm to print the minimum number following that pattern.
Digits from 1-9 and digits can’t repeat.

• Time : O(|S|!)
• Space : O(1)

class Solution{
    bool helper(string& res, string& s, int pos, int mask, int last) {
        if(pos == s.length()) return true;
        for(int i = 1; i <= 9; i++) {
            if(mask & (1<<i)) continue;
            if(s[pos] == 'I' and i <= last) continue;
            if(s[pos] == 'D' and i >= last) continue;
            res.push_back(0b110000 | i);
            if(helper(res, s, pos + 1, mask | (1<<i), i))
                return true;
            res.pop_back();
        }
        return false;
    }
public:
    string printMinNumberForPattern(string S){
        string res = "";
        for(int i = 1; i <= 9; i++) {
            res.push_back(0b110000 | i);
            if(helper(res, S, 0, 1<<i, i))
                return res;
            res.pop_back();
        }
        return res;
    }
};

• Time : O(|S|)
• Space : O(|S|)

class Solution{
public:
    string printMinNumberForPattern(string S){
        string res = "";
        vector<int> st;
        int num = 1;

        for(auto& ch : S) {
            st.push_back(num++);
            while(ch == 'I' and !st.empty()) {
                res.push_back(st.back() | 0b110000);
                st.pop_back();
            }
        }
        st.push_back(num);
        while(!st.empty()) {
            res.push_back(st.back() | 0b110000);
            st.pop_back();
        }

        return res;
    }
};