C++ easiest solution O(n)

interview-questions
Tags: #<Tag:0x00007f242fa27420>

#1

vector Solution::findPerm(const string s, int B)
{
int n=s.size();
int mn=0; //Calculating the No . of Decreasing indexs.
for(int i=0;i<n;i++)
{
if(s[i]==‘D’)
{
mn++;
}
}
int start=mn+1; //staring with mn+1 means that we are reserving the first mn terms for the D indexes.
vectorans;
ans.push_back(mn+1);
for(int i=0;i<n;i++)
{
if(s[i]==‘I’)
{
start+=1; //Every time you come accross ‘I’ increment the value of start.
ans.push_back(start);
continue;
}
if(s[i]==‘D’)
{
ans.push_back(mn);
mn–;
}
}
return ans;
/for those of you who are thinking that it can be possible that we could have pushed negative
terms or terms greater than n.
It is not possible because
we already left the first mn terms to be pushed for D terms
and if we see that mn+1+mx=n
so it we never go out of range.
/
}