# C++ Very Easy-to-Understand O(n) Solution with Explanation

• My idea is very simple (just read the example first if my explanation is not clear):
Count how many D's, say k D's, then push the smallest k + 1 available numbers reversely to the result array. For I's it's even simpler, just push the smallest available number to the result array one by one.
The only exceptional case is when entering I from D, here you need to pop one earlier value. See the example:

e.g. DDDIIIDDD

[DDD]IIIDDD ( [] = just scanned characters)
3 D's, so push the smallest 4 numbers:
Result:4,3,2,1

DDD[III]DDD
3 I's, so push the next 3 smallest numbers, which are 5, 6, 7.
Result:4,3,2,1,5,6,7,

DDDIII[DDD]
3 D's, and the previous one was I. So pop last pushed value 7, and push next 4 smallest numbers: 10, 9, 8, 7
Result:4,3,2,1,5,6,10,9,8,7

Done

Idea is just as easy as this. The implementation takes some attention to get right though.

``````class Solution {
public:
vector<int> findPermutation(string s) {
vector<int> result;
s.push_back('I'); //Force to run one more round after i == s.size()
int count = 0;
for (int i = 0; i < s.size(); ++ i)
{
if (s[i] == 'D')
{
count ++;
continue;
}
if (i == 0 || s[i - 1] == 'D' )
{
if (result.size() > 0)
result.pop_back();
result.push_back(result.size() + count + 1);
}
int base = result.size() - 1;
while (count > 0)
{
result.push_back(base + count);
count --;
}
result.push_back(result.size() + 1);
}
result.pop_back(); // Don't need the additional one.
return result;
}
};
``````

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