Greedy String Construction

Lexicographically smallest construction requires more than taking the smallest currently legal character. A choice must also leave a feasible completion. We use the same no-equal-adjacent multiset constraint as the frequency lesson, but now optimize lexical order. An exact suffix-feasibility test lets the algorithm try letters from a to z and safely commit to the first completable one.

Prerequisites: Frequency Counting lesson; induction; lexicographic order.

Build the idea

1. Distinguish local legality and completion

   A letter differing from the previous one is locally legal, but it may strand a repeated letter. From counts a:1,b:2, starting with a leaves bb, which cannot be completed; bab is the only valid arrangement. Thus a naive smallest-legal-letter rule fails. The output must preserve every input frequency, not merely choose some convenient subset.

2. Test a blocked-first suffix

   With m remaining positions and previous letter p forbidden at the next position, require count[p]≤floor(m/2) and each other count≤ceil(m/2). The previous letter needs a separator before every remaining copy; any other letter can also occupy the first position. The formula in feasible implements both cases using (m+(c!=previous))/2. For previous=−1 every symbol gets the unrestricted bound.

   $$\mathrm{count}\left[c\right]\le \mathrm{floor}\left(\right(m+[c\ne \mathrm{previous}])/2)$$

3. Correctness proof: feasibility and first difference

   The bound is sufficient: choose a largest-count allowed letter. For odd m, any letter at ceil(m/2) is unique and must be chosen; for even m, decrementing any largest allowed count meets the next blocked-letter bound. The residual bounds persist, giving a completion by induction. The lexical algorithm therefore tests a genuine oracle. At each position it selects the smallest letter having any completion; every valid competing string with a smaller next letter would contradict that test. Induct on the common prefix, or compare the first differing position, to prove global lexical minimality.

4. Trace aaabbc

   Try a: the residual counts can still be completed, so accept it. Next a is forbidden; b is the first completable choice. Continue with a,b,a,c, producing ababac. For abb, the initial a trial fails because the remaining b count exceeds its suffix capacity; restore its count and try b instead, producing bab. Restoring failed trials is necessary for later choices.

5. Read the implementation and scope

   count holds remaining frequencies; previous records the fixed prefix’s final letter; remaining controls the suffix length. Tentatively decrement a candidate, call feasible, restore if rejected, and break only on acceptance. Initial infeasibility prints IMPOSSIBLE. This exact oracle is specific to adjacent inequality; adding forbidden pairs, quotas or longer cooldowns can invalidate its sufficiency.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<array>
bool feasible(const std::array<int,26>&count,int previous,int remaining){
    for(int c=0;c<26;++c){
        if(count[c]>(remaining+(c!=previous))/2){
            return false;
        }
    }
    return true; // Previous symbol cannot occupy the first position of the suffix.
}
int main(){
    std::string input;
    std::cin>>input;
    std::array<int,26>count{};
    for(char c:input){
        ++count[c-'a'];
    }
    int remaining=input.size(),previous=-1;
    std::string result;
    if(!feasible(count,previous,remaining)){
        std::cout<<"IMPOSSIBLE\n";
        return 0;
    }
    while(remaining){
        for(int c=0;c<26;++c){
            if(c!=previous&&count[c]){
                --count[c];
                if(feasible(count,c,remaining-1)){
                    result+=char('a'+c);
                    previous=c;
                    --remaining;
                    break;
                }
                ++count[c];
            }
        }
    }
    std::cout<<result<<'\n';
}

Complexity analysis

O(σ²n) time: each of n positions may try σ letters and scan σ counts, with σ=26. O(n+σ) space including output. Treating the alphabet as fixed gives linear time in n with a larger constant than the max-heap any-arrangement method.

Example input and output

Read one nonempty lowercase string of length≤100000. Print the lexicographically smallest rearrangement with no equal adjacent letters, or IMPOSSIBLE.

Input

aaabbc

Output

ababac

Each accepted smallest letter leaves a feasible suffix; choosing a twice consecutively is forbidden, and failed trials would be restored.

Practical applications

Use prefix construction when you can decide whether a partial choice admits some completion. Feasibility may come from counts, matching, flow or DP; the lexical first-difference proof is reusable, but the oracle and its cost must be re-established for each problem.

Check your understanding

Why is starting with a wrong for the multiset abb?

Put it into practice

Enumerate all permutations of short multisets and compare the first valid string.