For coding convenience, we pre-process the secrete signature string `s`

by `s += 'I'`

. Now `s`

can be partitioned into several disjoint segments in format

`s = [D...DI] + [D...DI] + ... [D...DI]`

,

where each segment `[D...DI]`

represents a decreasing subsequence in `[1, n]`

and there must be a "jump" from one segment to next. Note that there may be zero `D`

's in a segment (e.g., `[I]`

).

With greedy method, we can create the lexicographically smallest valid sequence:

- For first segment
`D...DI`

(length =`L`

), pick`L`

smallest numbers from initial range`[1, n]`

and push into result vector`res`

in decreasing order; - Remove those
`L`

numbers from range`[1, n]`

; - Go to next segment and repeat steps 1 and 2 until exhausting entire string
`s`

.

```
vector<int> findPermutation(string s) {
vector<int> res; s += 'I';
for (int i = 0; i < s.size(); i = res.size())
for (int j=s.find('I',i)+1; j > i; res.push_back(j--)) ;
return res;
}
```

Alternatively, we can also use `std::reverse`

in a single loop:

```
vector<int> findPermutation(string s) {
vector<int> res((s += 'I').size());
for (int i = 0, j = 0; i < s.size() && (res[i] = ++i); )
if (s[i-1] == 'I') reverse(res.begin()+j, res.begin()+i), j = i;
return res;
}
```