DI String Match

Problem

A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:

• s[i] == 'I' if perm[i] < perm[i + 1], and
• s[i] == 'D' if perm[i] > perm[i + 1].

Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

Constraints

• 1 <= s.length <= 105
• s[i] is either 'I' or 'D'.

Solution

The problem DI String Match can be solved using a sliding window technique. For a given range [0, n], when s[0] is I, selecting 0 ensures that perm[0] < perm[1] no matter which integer comes next. Similarly, when s[0] is D, selecting n ensures that perm[0] > perm[1]. This same process can be repeated with the previously selected integers being excluded from the range until a valid permutation is found.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    vector<int> diStringMatch(string s)
    {
        int left = 0, right = s.length();
        vector<int> ret;

        s += s.back();
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == 'I')
            {
                ret.push_back(left);
                left += 1;
            }
            else if (s[i] == 'D')
            {
                ret.push_back(right);
                right -= 1;
            }
        }

        return ret;
    }
};