Increasing String INCREAST Solution
You are given a string S, consisting of lowercase English letters. You can do the following operation at most once :
- Choose a subsequence of the string S, then remove it from S and concatenate the subsequence at the end of the remaining string.
Find the lexicographically minimum string that can be obtained by performing this operation at most once on S.
Note that:
- A string A is a subsequence of a string B if A can be obtained by deleting several (possibly, zero or all) characters from B.
- Given two strings of the same length A and B, we say that A is lexicographically smaller than B if there exists an index ii such that A1=B1,A2=B2,…,Ai−1=Bi−1 and Ai<Bi.
Input Format
- The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains a string S.
Output Format
For each test case, print a single line containing the lexicographically minimum string which can be obtained from S by performing the given operation at most once.
Constraints
- 1≤T≤2⋅105
- 1≤|S|≤105
- S contains only lowercase English letters.
- Sum of |S| over all test cases does not exceed 106.
Subtasks
- Subtask 1 (100 points): Original constraints
Sample Input 1
4
aba
abcd
cbcdbef
fabcdac
Sample Output 1
aab
abcd
bbccdef
aacfbcd
Explanation
Test case 1: It is optimal to choose the subsequence b, then remove and concatenate the subsequence at the end of the remaining string aa. Hence the final string is aa+b=aab.
Test case 2: The given string is already lexicographically minimum.
Test case 3: It is optimal to choose the subsequence ccdef, then remove and concatenate the subsequence at the end of the remaining string bb. Hence the final string is bb+ccdef=bbccdef.
SOLUTION
Program Python: Increasing String INCREAST Solution in Python
def inc(s):
global f
global l1
global l2
sr=s[::-1]
n=len(s)
m=min(list(s))
i1=s.index(m)
i2=n-sr.index(m)-1
if m<f:
for i in s[:i2+1]:
if i!=m:
l2.append(i)
if f=="zz":
f=i
else:
l1.append(i)
if i2+1<n:
inc(s[i2+1:])
else:
for i in s:
a="".join(l2)
if a+i<i+a:
l2.append(i)
else:
l1.append(i)
for i in range(int(input())):
s=str(input())
l1=[]
l2=[]
f="zz"
inc(s)
print("".join(l1+l2))
Program C++: Increasing String INCREAST Solution in C++
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
char k = *min_element(s.begin(), s.end());
string front = "";
string back = "";
bool l = true;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == k && l)
{
front += s[i];
k = *min_element(s.begin() + i + 1, s.end());
if (back.size() && k > back[0])
{
l = false;
}
else if (back.size() > l && k == back[0])
{
string t = back + k;
string y = k + back;
if (t < y)
{
l = false;
}
}
}
else
{
back += s[i];
}
}
cout << front + back << '\n';
}
return 0;
}
December Long Challenge 2021 Solution
- List of Lists LISTLIST Solution Codechef
- Valleys and Hills VANDH Solution Codechef
- Rock Paper Scissors ROPASCI Solution Codechef
- Squares Counting GRIDSQRS Solution Codechef
- Pyramid Traversal PYRAMIDMOVES Solution Codechef
- Increasing String INCREAST Solution Codechef
- Utkarsh and Placement tests UTKPLC Solution Codechef
- Check Mate CHECKMATE Solution Codechef