-
Notifications
You must be signed in to change notification settings - Fork 52
/
Question66.cpp
64 lines (55 loc) · 1.57 KB
/
Question66.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
You are given a string s and a robot that currently holds an empty string t. Apply one of the following operations until s and t are both empty:
Remove the first character of a string s and give it to the robot. The robot will append this character to the string t.
Remove the last character of a string t and give it to the robot. The robot will write this character on paper.
Return the lexicographically smallest string that can be written on the paper.
Example 1:
Input: s = "zza"
Output: "azz"
Explanation: Let p denote the written string.
Initially p="", s="zza", t="".
Perform first operation three times p="", s="", t="zza".
Perform second operation three times p="azz", s="", t="".
*/
#include <bits/stdc++.h>
using namespace std;
char minchar(map<char,int>&m){
for(auto &val : m){
if(val.second>0) return val.first;
}
return 'a';
}
void answer(string s){
map<char,int>m;
for(auto &val : s){
m[val]++;
}
/*
We created a stack
as it follows
LIFO
element is added at last and element is removed from first
which states the question
*/
stack<int>t;
string ans="";
for(auto &i:s){
t.push(i);
m[i]--;
while(!t.empty() && t.top()<=minchar(m)){
ans+=t.top();
t.pop();
}
}
while(!t.empty()){
ans+=t.top();
t.pop();
}
cout << ans << endl;
}
int main() {
string s;
cin >> s;
answer(s);
return 0;
}