Leetcode 484. Find Permutation

484. Find Permutation

We can reverse the range of ‘D’ as shown in the figure below.

Image from HERE

class Solution {
public:
    vector<int> findPermutation(string s) {
        const int n = s.length() + 1;
        vector<int> ret(n);
        for (int i = 1; i<= n; ++i)
        {
            ret[i-1] = i;
        }
        int left = 0, right = 0;
        for (int i = 1; i < n; ++i)
        {
            if (s[i-1] == 'I')
            {
                
                if (i-2 >= 0 && s[i-2] == 'D')
                {
                    reverse(ret.begin() + left, ret.begin() + i);
                }
                left = i;
            }
            else if (i == n-1 && s[i-1]=='D')
            {
                reverse(ret.begin() + left, ret.end());
            }
        }
        return ret;
    }
};
//  IIII     II(DD)
// 12345    12(345)
//  IIIIII.  II(DD)I(D)
// 1234567. 12(345)(67)