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

1. 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 a’s to the end and then reverse it.

so 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) ‘d’ is smallest. Therefore we group d’s up till this point and we get the string sddcacdfac. But after it we get c as the next smallest character so we start grouping ‘c’. Then at index 5 we hit a global minimum which is ‘a’ so only a’s can be grouped.

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 d’s together also but since we can only group one at a time we prioritize the smallest to achieve the lexicographically smallest string.

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();
    }
}