# 4-liner C++ O(N) greedy method in two versions (detailed explanation)

• 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:

1. 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;
2. Remove those `L` numbers from range `[1, n]`;
3. 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;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.