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.
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]
Constraints:
1 <= s.length <= 105
s[i] is either 'I' or 'D'.
Solutions
Solution 1: Greedy Algorithm
We can use two pointers low and high to represent the current minimum and maximum values, respectively. Then, we traverse the string s. If the current character is I, we add low to the result array, and increment low by 1; if the current character is D, we add high to the result array, and decrement high by 1.
Finally, we add low to the result array and return the result array.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the string s.