Increasing String INCREAST Solution Codechef

Page Contents

Increasing String INCREAST Solution

You are given a string SS, consisting of lowercase English letters. You can do the following operation at most once :

Choose a subsequence of the string SS, then remove it from SS 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 SS.

Note that:

A string AA is a subsequence of a string BB if AA can be obtained by deleting several (possibly, zero or all) characters from BB.
Given two strings of the same length AA and BB, we say that AA is lexicographically smaller than BB if there exists an index ii such that A1=B1,A2=B2,…,Ai−1=Bi−1A1=B1,A2=B2,…,Ai−1=Bi−1 and Ai<BiAi<Bi.

Input Format

The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
The first and only line of each test case contains a string SS.

Output Format

For each test case, print a single line containing the lexicographically minimum string which can be obtained from SS by performing the given operation at most once.

Constraints

1≤T≤2⋅1051≤T≤2⋅105
1≤|S|≤1051≤|S|≤105
SS contains only lowercase English letters.
Sum of |S||S| over all test cases does not exceed 106106.

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 11: It is optimal to choose the subsequence bb, then remove and concatenate the subsequence at the end of the remaining string aaaa. Hence the final string is aa+b=aabaa+b=aab.

Test case 22: The given string is already lexicographically minimum.

Test case 33: It is optimal to choose the subsequence ccdefccdef, then remove and concatenate the subsequence at the end of the remaining string bbbb. Hence the final string is bb+ccdef=bbccdefbb+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;

}