C. Minimal string

C. Minimal string

Link for the problem: C. Minimal string

SOLUTION:

To solve this problem, we have to do a little precomputation. Let the given string v S and its length be l. Now we make another character array C such that C[i] is the smallest element from i to l-1. The precomputation can be done in O(n) by starting from right end of string and using already computed value.
Now, for every element S[i], there is a C[i].  To solve this problem we use stack.
For every element S[i], we follow operations:-
1.)  If stack is empty, push s[i].
2.) Else, while c[i] is greater than or equal to top of stack, print the top for answer and then pop. Push the s[i].
After processing for all S[i], empty the stack by printing and popping the top.

CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    stack<char> s;
    string s1;
    cin>>s1;
    int l=s1.length(),i,j,k;
    char c[l];
    c[l-1]=s1[l-1];
    for(i=l-2;i>=0;i--)
    {
        c[i]=min(s1[i],c[i+1]);
    }
    for(i=0;i<l;i++)
    {
        while(!s.empty()&&c[i]>=s.top())
        {
                cout<<s.top();
                s.pop();
        }
        s.push(s1[i]);
    }
    while(!s.empty())
    {
        cout<<s.top();
        s.pop();
    }
    return 0;

}