PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Soumyadeep Pal
Tester: Lavish Gupta
Editorialist: Taranpreet Singh
DIFFICULTY
Easy-Medium
PREREQUISITES
Observations
PROBLEM
Given a string S, you can perform the following operation at most once. Choose a subsequence of S, remove it from S and append it at the end of S in the same order as it originally appeared in S.
Find the lexicographically smallest string which can be obtained.
QUICK EXPLANATION
- The subsequence of characters not chosen shall form a non-decreasing sequence of characters.
- The first character of chosen subsequence would not be strictly smaller than the last character of the non-chosen subsequence.
EXPLANATION
This problem requires a lot of observations. Instead of focusing on the subsequence of characters chosen, let’s focus on which characters are not chosen. Those characters remain at their own places, in the original order, and they appear before the chosen characters in the final string.
Observation 1: The subsequence of characters not chosen form a non-decreasing subsequence.
Proof: Let’s assume that both positions p and q are not chosen in subsequence, and p \lt q and S_p \gt S_q holds. This way, S_q appears before S_p. We can choose to include position q in subsequence, so that S_p appears first, resulting in a lexicographically smaller subsequence. This happens for each inversion pair. Hence, after removing all inversions, the characters not chosen form an increasing subsequence.
For example, for string pqpqrqs, the characters not chosen form string ppqqs and chosen characters form string qr.
Now that we have a non-decreasing subsequence, we need to decide what prefix of this ppqqs needs to be kept non-chosen. In this case, the best we can obtain is ppqqqrs.
First of all, the characters strictly greater than the first character of chosen subsequence needs to be removed. For example, here, the character s must actually be chosen, as not choosing s is sub-optimal.
We cannot decide whether we should keep the qqq, or include them in operation.
For example, consider strings aadeacd, it is optimal to choose subsequence de, and for string aadcacd, it is optimal to choose dcd. How to decide whether the last d should be chosen or not?
The last d must be included in subsequence, only if the appending the chosen subsequence results in a smaller subsequence. For the first string, including d would have resulted in aaacded which is larger than aaacdde.
The easiest way to decide is by iterating over chosen string, and if it has first character same as last character of non-chosen subsequence, find the first character in chosen subsequence different from the first character. For first string, that was e, which is greater than d. So we should not remove d from the end.
For second string, the next character was c, which is smaller than d, so it was optimal to remove d from the end of non-chosen characters.
The correct answer for string aadeacd is aaacdde, and the correct answer to aadcacd is aaacdcd. Try figuring out on a notebook.
Implementation
Keep a boolean array representing whether or not some position is included in the operation or not. For finding non-decreasing subsequence of characters not chosen, a stack can be used. At each character, pop from stack all characters greater than the current character.
TIME COMPLEXITY
The time complexity is O(|S|) per test case.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
template <class T> ostream &operator << (ostream &os, const vector<T> &p) { os << "["; for (auto&it : p) os << it << " "; return os << "]";}
template <class S, class T> ostream &operator << (ostream &os, const pair<S, T> &p) { return os << "(" << p.first << "," << p.second << ")";}
#ifndef ONLINE_JUDGE
#define deb(...) dbs(#__VA_ARGS__,__VA_ARGS__)
template <class T> void dbs(string str, T t) { cerr << str << ":" << t << "\n";}
template<class T, class...S> void dbs(string str, T t, S... s) { int idx = str.find(','); cerr << str.substr(0, idx) << ":" << t << ","; dbs(str.substr(idx + 1), s...);}
#else
#define deb(...){}
#endif
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pr(x) {cout << x << '\n'; return;}
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
template<class T> inline T Bit(T x, int i) { return (x >> i) & 1;}
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
clock_t start = clock();
void solve() {
string s; cin >> s;
int n = s.size();
vector<int> last(26, -1);
for (int i = 0; i < n; i++) {
last[s[i] - 'a'] = i;
}
int dig = 0;
int mx = 26;
string ans = s, ans1, ans2;
for (int i = 0; i < n; i++) {
while (dig < 26 && i > last[dig]) dig++;
if (dig == mx) {
string ans3 = ans2, ans4;
for (int j = i; j < n; j++) {
if (s[j] == ('a' + mx)) {
ans4.push_back(s[j]);
}
else {
ans3.push_back(s[j]);
}
}
ans2 += s.substr(i);
ans = min(ans, ans1 + min(ans2, ans4 + ans3));
break;
} else if (dig > mx) {
ans = min(ans, ans1 + ans2 + s.substr(i));
break;
}
if (s[i] == ('a' + dig)) {
ans1.push_back(s[i]);
} else {
if (mx == 26) mx = (s[i] - 'a');
ans2.push_back(s[i]);
}
if (i == n - 1) ans = min(ans, ans1 + ans2);
}
assert(sz(s) == sz(ans));
cout << ans << '\n';
}
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 200000;
const int MAX_N = 100000;
const int MAX_SUM_LEN = 1000000;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
// int n;
void solve()
{
//cout << "start" << endl ;
string str ;
str = readStringLn(1 , MAX_N) ;
int n = str.size() ;
max_n = max(max_n , n) ;
sum_len += n ;
int suff_min[n] ;
//cout << str << endl ;
for(int i = 0 ; i < str.size() ; i++)
{
int val = (str[i] - 'a') ;
assert(val >= 0 && val < 26) ;
suff_min[i] = val ;
}
for(int i = n-2 ; i >= 0 ; i--)
{
suff_min[i] = min(suff_min[i+1] , suff_min[i]) ;
}
int unused_start = 27 ;
vector<int> retain(n) ;
for(int i = 0 ; i < n ; i++)
{
int val = (str[i] - 'a') ;
if(val == suff_min[i] && val < unused_start)
{
retain[i] = 1 ;
continue ;
}
if(val == unused_start && val == suff_min[i])
{
retain[i] = 2 ;
continue ;
}
if(unused_start == 27)
{
retain[i] = 0 ;
unused_start = val ;
}
}
// for(int i = 0 ; i < n ; i++)
// cout << retain[i] << ' ';
// cout << endl ;
string ans1 , ans2 ;
for(int i = 0 ; i < n ; i++)
{
if(retain[i] == 1)
ans1 += str[i] ;
if(retain[i] == 1 || retain[i] == 2)
ans2 += str[i] ;
}
for(int i = 0 ; i < n ; i++)
{
if(retain[i] == 0 || retain[i] == 2)
ans1 += str[i] ;
if(retain[i] == 0)
ans2 += str[i] ;
}
// cout << ans1 << endl ;
// cout << ans2 << endl ;
cout << min(ans1 , ans2) << endl ;
return ;
}
signed main()
{
//fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
int t = 1;
t = readIntLn(1,MAX_T);
for(int i=1;i<=t;i++)
{
solve() ;
}
assert(getchar() == -1);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_len << '\n';
cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class INCREAST{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
char[] S = n().toCharArray();
Stack<Integer> stack = new Stack<>();
boolean[] added = new boolean[S.length];
for(int i = 0; i< S.length; i++){
while(!stack.isEmpty() && S[stack.peek()] > S[i])added[stack.pop()] = false;
stack.add(i);
added[i] = true;
}
StringBuilder ans = new StringBuilder(), st = new StringBuilder();
for(int i = 0; i< S.length; i++)if(added[i])ans.append(S[i]);else st.append(S[i]);
boolean bef = true;
for(int i = 1; i< st.length(); i++){
if(st.charAt(i) != st.charAt(i-1)){
bef = st.charAt(i) < st.charAt(i-1);
break;
}
}
int ind = ans.length();
if(st.length() > 0 && st.charAt(0) <= ans.charAt(ans.length()-1)){
for(int i = 0; i< ans.length(); i++){
if(bef && ans.charAt(i) >= st.charAt(0)){
ind = i;
break;
}
if(!bef && ans.charAt(i) > st.charAt(0)){
ind = i;
break;
}
}
}
StringBuilder output = new StringBuilder();
for(int i = 0, cnt = 0; i< S.length; i++){
if(added[i]){
if(cnt < ind){
output.append(S[i]);
cnt++;
}
else added[i] = false;
}
}
for(int i = 0; i< S.length; i++)if(!added[i])output.append(S[i]);
pn(output.toString());
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new INCREAST().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
