class Solution {
public:
    vector<int> diStringMatch(string S) {
        int low = 0;
        int high = S.length();
        std::vector<int> out(high+1);

        int ii=0;
        for (const auto c:S) {
            if (c=='I')
                out[ii++]=low++;
            else
                out[ii++]=high--;
        }
        if (S[ii-1]=='D')
            out[ii]=low;
        else
            out[ii]=high;
        return out;
    }
};