Greedy Algorithms with Frequency Counting

Frequency counts reveal which resource is hardest to place. We rearrange a lowercase multiset so equal letters are never adjacent. Choosing a most frequent currently allowed letter prevents a dominant symbol from being stranded. A heap supplies the largest remaining count while a held previous letter enforces the adjacency restriction. The output is any valid rearrangement, not necessarily the lexicographically smallest one.

Prerequisites: Frequency arrays; Priority Queues; induction. Related existing lessons: Priority Queues and Binary Heaps.

Build the idea

1. Derive a necessary capacity bound

   If the most common letter appears M times in a string of length n, its copies need at least M−1 separating other letters. There are n−M such separators, so M≤ceil(n/2) is necessary. This condition is also sufficient for an unrestricted starting position. Merely counting distinct letters would miss a highly unbalanced input such as aaaaab.

2. Hold the previous symbol out

   Build counts for the 26 letters and a max-heap keyed by remaining frequency, then smaller letter on ties. Pop the largest available count, output that letter and decrement it. Only afterward return the previously held count to the heap. The newly output letter stays held until the next iteration, so it cannot be chosen twice consecutively.

   $$M\le \mathrm{ceil}(n/2)$$

3. Correctness proof: preserve suffix feasibility

   For m remaining positions with previous letter p forbidden first, feasibility is equivalent to count[p]≤floor(m/2) and every other count≤ceil(m/2). Choosing a maximum-count allowed letter preserves these bounds: if m is odd, any count at the larger bound is unique and must be chosen; if m is even, all counts are at most m/2 and decrementing the chosen one meets the next forbidden-letter bound. Induction constructs a suffix whenever feasible. If the heap empties with a held count left, the remaining instance cannot be completed.

4. Trace the sample

   For aaabbc, choose a (remaining a2,b2,c1), then b while a is held, then a, then b, then a, then c. The result ababac has the same counts and no adjacent equality. The heap may produce a different valid arrangement on ties if its tie-breaker changes; only validity and impossibility are mathematically significant here.

5. Connect counts to resource decisions

   The array is the compact multiset representation, the heap orders urgency, and previous is a one-step cooldown. General cooldown lengths require a different release queue and a new feasibility analysis. If lexical order is the objective, largest frequency is not automatically the desired first letter; the dedicated string-construction lesson tries letters in order while retaining a completion test.

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

#include<iostream>
#include<string>
#include<array>
#include<queue>
#include<utility>
int main(){
    std::string input;
    std::cin>>input;
    std::array<int,26>count{};
    for(char c:input){
        ++count[c-'a'];
    }
    // A held previous symbol cannot be taken in the immediately following position.
    std::priority_queue<std::pair<int,int>>ready;
    for(int c=0;c<26;++c){
        if(count[c]){
            ready.push({count[c],-c});
        }
    }
    std::pair<int,int>previous{0,0};
    std::string answer;
    while(!ready.empty()){
        auto current=ready.top();
        ready.pop();
        answer+=char('a'-current.second);
        --current.first;
        if(previous.first>0){
            ready.push(previous);
        }
        previous=current;
    }
    std::cout<<(answer.size()==input.size()?answer:"IMPOSSIBLE")<<'\n';
}

Complexity analysis

O(n+σ log σ+n log σ) time, O(n+σ) storage including output, with σ≤26. Counting is linear; each output step performs at most one heap pop and push. With fixed alphabet this is O(n).

Example input and output

Read one nonempty lowercase string, length at most 100000. Print a rearrangement with no equal adjacent letters, or IMPOSSIBLE. Ties prefer smaller letters, making the sample deterministic.

Input

aaabbc

Output

ababac

The two b letters and one c separate the three a letters. The held previous letter prevents immediate reuse.

Practical applications

Use frequency feasibility and an urgency heap for rearrangement and cooldown-like resource problems under the stated model. For more complex constraints, a count bound may only be necessary; prove sufficiency before treating it as a completion oracle.

Check your understanding

Why is the most recently used letter temporarily absent from the heap?

Put it into practice

Enumerate all rearrangements of short multisets and check the maximum-frequency bound.