Maximum Expressions

You’re given a string S containing digits 0–9 and operators '+' and '-', and it is a valid expression.

You must rearrange all characters of S to form another valid expression that, when evaluated (left to right with normal arithmetic), has maximum possible value.

If multiple answers yield the same maximum value, any one is acceptable.

Valid Expression Rules

A string S is valid if:

First character is not + or - (must be a digit).
Last character is not + or - (must be a digit).
No + or - are adjacent.
⇒ Operators strictly alternate with numbers.

Numbers may have leading zeros; +0 and -0 are allowed.

Core Idea

We can rearrange all characters freely:

Let total digit count be D.
Let operator count (number of + and -) be O.
For a valid expression, operators and numbers alternate:

Each operator needs two numbers (before and after).
If we have O operators, we need O + 1 numbers (i.e., number tokens).
Total digits D can be split into O + 1 numbers by distributing digits among them (possibly with leading zeros).

Thus:

O = count('+') + count('-') is fixed.
We must form exactly O+1 numbers using all D digits.
When evaluated left-to-right:

N0 op1 N1 op2 N2 ... opO NO

Total value:

Value=N0+(±N1)+(±N2)+...+(±NO)

Each number contributes either positive or negative based on the operator before it:

N0 is always positive.
Each + before Ni → Ni has positive contribution.
Each - before Ni → Ni has negative contribution.

So to maximize value:

Make the sum of positive-contribution numbers as large as possible.
Make the sum of negative-contribution numbers as small as possible (i.e., remaining small digits grouped into these).

We are free to:

Choose which operators are + and which are - (we only know counts of each).
Choose which numbers go in which positions.
Choose how digits are grouped into each number.

Optimal Strategy:

Let:

Cplus = count of '+' in original S.
Cminus = count of '-' in original S.
Total operators O = Cplus + Cminus.
Total numbers numTokens = O + 1.

Number of positive-contribution tokens:

N0 is positive.
After any '+' operator, the next number is positive.
So:

positiveTokens=1+Cplus

Negative-contribution tokens:

negativeTokens=numTokens-positiveTokens=(O+1)-(1+Cplus)=Cminus

So:

Exactly positiveTokens = Cplus + 1 numbers will be added.
Exactly negativeTokens = Cminus numbers will be subtracted.

We want to:

Make the positive tokens large by giving them the largest digits.
Make the negative tokens small by giving them the smallest digits.
Use longest-length numbers for positive tokens and shorter numbers for negative tokens, since more digits → bigger number.

Concrete Digit Assignment:

Collect all digits from S into an array digits.
Sort digits in descending order.
We will create numTokens = O + 1 numbers.

Assign one digit to each token first so they’re all non-empty.
Then distribute the remaining digits.

Positive tokens should, in total, receive the largest digits:

We know how many positive tokens: posCount = Cplus + 1.
We know how many negative tokens: negCount = Cminus.

Optimal distribution:

Give 1 digit to each negative token first (from the smallest digits).
Give 1 digit to each positive token (from the largest remaining digits).
All remaining digits (still largest ones) should be appended to one positive token (e.g., the first positive token), making it huge.

Why?

Any extra digit added to a positive token increases value.
Any extra digit added to a negative token hurts value.
So we never give extra digits to negative tokens.

Constructing Operators and Tokens Order:

We must preserve counts:

Exactly Cplus plus signs.
Exactly Cminus minus signs.

We can choose any order. To maximize:

Make as many positive tokens as possible.
But posCount is fixed, so order doesn’t change how many are positive or negative, only which tokens are negative.

Simplest:

Put all - operators towards the end, so most numbers at the front are positive.

A simple pattern:

Start with N0 (positive).
Then:

First put all + operators, each followed by a positive token.
Then put all - operators, each followed by a negative token.

Thus token roles:

Token index 0 .. Cplus → positive.
Token index Cplus+1 .. Cplus+Cminus → negative.

Algorithm Summary

For each test case:

Read S, count Cplus, Cminus, and collect all digits in digits.
Sort digits in ascending order.
posCount = Cplus + 1, negCount = Cminus, numTokens = posCount + negCount.
Create tokens as list of strings of length numTokens.
Assign 1 digit per negative token (smallest digits):

For i in 0 .. negCount-1:

tokens[posCount + i] += smallest available digit

Assign 1 digit per positive token (largest digits):

For i in 0 .. posCount-1:

tokens[i] += largest available digit

Put all remaining digits into tokens[0] (a positive token), appending them as largest-first or smallest-first (both are fine as they all belong to a positive number; to be consistent, use remaining largest-first).
Build operator sequence: