Construct a Permutation Matching Consecutive Increase and Decrease Signs
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
For `n = s.length`, return any permutation of all integers0 through n whose adjacent comparisons match s. An I requires `perm[i] < perm[i+1]`; a D requires `perm[i] > perm[i+1]`.
```cpp
class Solution {
public:
vector<int> diStringMatch(string s);
};
```
### Examples
**Example 1:**
```text
Input: s = "IID"
Output: [0,1,3,2]
Explanation: The adjacent comparisons are0<1,1<3,and3>2.
```
**Example 2:**
```text
Input: s = "D"
Output: [1,0]
Explanation: The only required comparison is decreasing.
```
### Constraints
- `1 <= s.length <= 10^5`.
- Every character is I or D.
### Contract considerations
Any valid permutation is accepted; the source does not prescribe a canonical answer.
```hint Read the boundary condition
Choose a value that guarantees the current comparison against every possible remaining value.
```
### What a Strong Answer Covers
Any valid permutation is accepted; the source does not prescribe a canonical answer.
### Follow-up Questions
Optional practice extension, separate from the original task: How would the output requirement change if the lexicographically smallest valid permutation were required?
Overview: Construct a Permutation Matching Consecutive Increase and Decrease Signs. For n = s.length, return any permutation of all integers0 through n whose adjacent comparisons match s.