942. DI String Match

1. Description

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.

2. Example

Example 1

Input: s = “IDID”
Output: [0,4,1,3,2]

Example 2

Input: s = “III”
Output: [0,1,2,3]

Example 3

Input: s = “DDI”
Output: [3,2,0,1]

3. Constraints

• 1 <= s.length <= 10$^{5}$
• s[i] is either ‘I’ or ‘D’.

4. Solutions

Greedy

n = str.size()
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<int> diStringMatch(const string &str) {
        vector<int> result(str.size() + 1);
        int left = 0, right = str.size();
        for (int i = 0; i < str.size(); ++i) {
            if (str[i] == 'I') {
                result[i] = left;
                ++left;
            } else {
                result[i] = right;
                --right;
            }
        }

        result[str.size()] = result[str.size() - 1] + (str.back() == 'I' ? 1 : -1);

        return result;
    }
};