Stack based solution (Also covers lexicographically smallest number thus produced)


#1
> vector<int> Solution::findPerm(const string A, int B) {
>     int n=1;
>     vector<int> ans;
>     stack<int> s;
>     s.push(n);
>     for(int i=0; i<A.length(); i++){
>         if(A[i]=='I'){
>             while(!s.empty()){
>                 ans.push_back(s.top()); 
>                 s.pop();
>             }
>             s.push(++n);
>         }
>         else{
>             s.push(++n);
>         }
>     }
>     while(!s.empty()){
>         ans.push_back(s.top());
>         s.pop();
>     }
>     return ans;
> }

#2

This doesn’t work in linear time, right?