Largest Remaining Password
National Olympiad — National round
Submission name: password.cpp
Problem summary
Delete exactly K digits from a positive decimal integer without changing the order of the remaining digits, to make the remaining number as large as possible. At least one digit remains.
Input
The original number as a digit string without leading zeros; K on the following line.
Output
The largest remaining number.
Constraints
Number length at most 10^6; 1≤K≤10^6 and K is smaller than the number length.
Worked example
An independently prepared example for this explanation.
Input
19234 2
Output
934
Solution analysis
- Maintain a stack of chosen digits.
- While deletions remain and the next digit exceeds the stack’s final digit, delete that final digit. Then append the new digit.
- If deletions remain after processing, delete from the end.
Why it works
At the first differing digit, the larger digit determines the larger fixed-length result. Replacing a smaller final digit with the incoming larger one is therefore optimal whenever a deletion is available. If digits are nonincreasing, removing the suffix retains the best prefix.
Watch out. Delete exactly K digits; equal digits do not justify an early deletion.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: At the first differing digit, the larger digit determines the larger fixed-length result.
// Replacing a smaller final digit with the incoming larger one is therefore optimal whenever a
// deletion is available.
#include<iostream>
#include<string>
#include<tuple>
#include<iomanip>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s,t;
int k;
cin>>s>>k;
for(char c:s){
while(k&&!t.empty()&&t.back()<c){
t.pop_back();
--k;
}
t.push_back(c);
}
t.resize(t.size()-k);
cout<<t<<'\n';
}