Easy solution with O(n) time complexity & explanation


#1

Find the number of 'I’s and 'D’s in the string, then find the n_I which is the minimum of the greater number arrangement and n_D is the maximum of the smaller number arrangement. Then apply the loop to arrange the numbers with the help of n_I and n_D.

vector Solution::findPerm(const string A, int B) {
int D=0, I=0;
for(int i=0; i<A.size(); i++){
if(A[i]== ‘D’)D++;
else I++;
}

int n_I=B-I+1;
int n_D=n_I-1;
cout << "n_I is: " << n_I << endl;
cout << "n_D is: " << n_D << endl;

vector<int>v;
for(int i=0; i<A.size(); i++){
    if(A[i]=='I' && i==0){v.push_back(1); v.push_back(n_I++);}
    else if(A[i]=='D' && i==0){v.push_back(n_D), n_D--; v.push_back(n_D), n_D--;}
    
    if(A[i]=='I' && i!=0){v.push_back(n_I++);}
    else if(A[i]=='D' && i!=0){v.push_back(n_D), n_D--;}
    
    
}
return v;

}