# Smallest Word

Based on codeforces 1043C

### Problem Statement

*Given a string S. Consider the prefixes in the fixed order: from the shortest to the largest. You want to get the lexicographically smallest possible word after you considers all prefixes.*

*At each prefix you can either reverse the current prefix or leave it as it is.*

*Print this lexicographically smallest string possible by performing the above operations on S.*

*For Lexicographic order **check wiki*

Example : Given a string **S** . You consider prefix lengths from **1 to |S|**(length of string) in that order. Example **S = **dbca**, |S| = 4**

Prefix Len(PL) 1 = d

PL 2 = db

PL 3 = dbc

PL 4 = dbca

The lexicographically smallest* achievable is ***abdc. **Here is how.

At *prefix len 2*. Reverse the string **db**. *S* is now **bdca**

At *prefix len 3*. Reverse the string **bdc**. *S* is now **cdba**

At *prefix len 4*. Reverse the string **cdba**. *S* is now **abdc**

Problem Link : You can test your solutions here

### Solution

- To get the lexicographically smallest string possible we need to have maximum smallest characters in the beginning succeeded by the next smallest and so on. Meaning it should be sorted in non decreasing order.

Example : *dsdcacdfac*

ideally the smallest that we would like is ** aacccdddfs **we will see if this achievable or not later.

2. We can always group similar character together with the above operation.

Example : ** ccbbcbc **and we want to accumulate c’s.

at prefix len 4 reverse to get *bbcccbc*

at prefix len 5 reverse to get *cccbbbc*

at prefix len 6 reverse to get *bbbcccc*

This way any similar character can be grouped together.

3. We want to accumulate all the smallest to the end. Then we perform one final reverse.

Example: ** abaaca **we accumulate all

**to the end and then reverse it.**

*a*’sso it becomes ** cbaaaa **and then we do one final reverse to get

**.**

*aaaabc*If smallest is always accumulated to the end. It is guaranteed that we would get the lexicographically smallest string.

4. Note here that we can only group one character at a time. We cannot group two characters. Therefore we always consider the current smallest character scanned up till now for grouping since that would give us lexicographically smallest.

Example :** dsdcacdfac**. Here till 3rd index(1 indexed) ‘

**is smallest. Therefore we group**

*d’***up till this point and we get the string**

*d’s*

**. But after it we get**

*sddcacdfac***as the next smallest character so we start grouping ‘**

*c***. Then at index 5 we hit a global minimum which is ‘**

*c’***so only**

*a’***can be grouped.**

*a’s*steps till index 3, group d’s to get : *sddcacdfac*

at index 5 we reverse to get : *acddscdfac*

at index 8 we reverse again to get : *fdcsddcaac*

finally at index 9 we reverse to get the smallest : *aacddscdfc*

Ideally we would like the ** c’s** and

**together also but since we can only group one at a time we prioritize the smallest to achieve the lexicographically smallest string.**

*d’s*Try to find the answer for example in given in point 1. You can verify your answer from the code below.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int i = 1;

string s;

void go(vector<ll> &pos, vector<ll> &ans) {

if(pos.size()==0) return;

ans[pos[0]] ^= 1;

if(pos.size() == 1) {

return;

}

for(int i = 1; i < pos.size(); i++) {

for(int j = pos[i-1]; j <= pos[i]; j++) {

if(s[j] != s[j+1] && s[j+1] == s[pos[i]]) {

ans[j] ^= 1;

ans[pos[i]] ^= 1;

break;

}

}

}

}

int solve()

{

cin>>s;

int i = 1;

auto smallest = s[0];

int n = s.length();

// ans[i] tells whether to reverse prefi of length (i+1)

vector<ll> ans(n,0), pos(n,0);

// find which swaps to make

while(i < n) {

if(s[i] < smallest) {

go(pos,ans);

pos.clear();

ans[i-1] ^= 1;

}

smallest = min(smallest,s[i]);

if(s[i] == smallest) {

if(pos.size() > 0 && i-pos.back() == 1)

pos.pop_back();

pos.push_back(i);

}

i++;

}

go(pos,ans);

// use ans(i) to reverse the original string

string out = s;

bool reversed = 0;

int beg = 0, end = n-1;

for (i = n-1; i >= 0; i--) {

reversed ^= ans[i];

if (reversed) out[beg++] = s[i];

else out[end--] = s[i];

}

cout << out << '\n';

return 0;

}

int main() {

int t; cin>>t;

while(t--) {

solve();

}

}