[CodeChef] Starters 78 — Balanced Suffix: the suffixes are just what's left

Published 1 October 2026

Problem: CodeChef — Balanced Suffix (Starters 78, difficulty 2447, same round as Solve More). Official editorial: BALSUFF — Editorial.

You’re given a string $S$ of length $N$ and an integer $K \ge 1$. Let $C$ be the set of characters appearing in $S$. A string is good if, in every suffix, any two characters of $C$ have frequencies differing by at most $K$. Characters of $C$ that don’t appear in a suffix count with frequency $0$. Print the lexicographically smallest good rearrangement of $S$, or $-1$.

Constraints: $N \le 10^5$, $\sum N \le 2 \cdot 10^5$, lowercase letters only.

Where I started¶

The first thing I wanted was the impossibility condition. The whole string is one of its own suffixes, so if $\max f - \min f > K$ over the full counts, no rearrangement can work.

My next thought was that if the full string passes, maybe the characters can be arranged freely. They can’t. $\min$ is taken over all of $C$, so it drops to $0$ as soon as some character runs out in a suffix, and a pile of one character at the end breaks it. For example, with $S = $ aabb and $K = 1$ the full counts are $2, 2$ and pass, but the arrangement aabb fails at the suffix bb ($f_a = 0$, $f_b = 2$). The answer here is abab.

For lexicographically smallest, the standard move is to fill positions left to right, each time taking the smallest character that still leaves a valid completion. What I couldn’t see was how to check “a valid completion still exists” quickly. Placing a batch of characters to test it would cost $O(\text{characters left})$, and I wanted something closer to $O(26)$.

Observation 1: the prefix decides every suffix¶

When I build the answer left to right, the suffix that starts right after the current prefix is exactly the multiset of characters I haven’t placed yet. Its order doesn’t matter, because the condition only looks at counts.

So the suffix condition at the next position is a condition on the remaining counts alone:

\[\max_{c \in C} r_c \;-\; \min_{c \in C} r_c \;\le\; K,\]

where $r_c$ is how many copies of $c$ are still unplaced, including zeros. Prefixes are never constrained, so I can ignore them completely. At one point I was told the prefix also had to stay balanced. It doesn’t; only suffixes are checked.

Observation 2: if the remaining counts pass, a completion exists¶

This is what makes the greedy cheap. Claim: if the remaining counts satisfy $\max - \min \le K$, the remaining characters can always be arranged so that every later suffix passes too.

Proof. Always place a character with the highest remaining count next. Suppose the counts satisfy $\max - \min \le K$ before the step.

If all counts in $C$ are equal, then after the step one count is $\max - 1$ and the rest are $\max$, so the spread is $1 \le K$. (This is where $K \ge 1$ matters.)
Otherwise $\max > \min$. Lowering a count that equals $\max$ leaves $\min$ unchanged, since that character was above the minimum, and $\max$ doesn’t go up. So the spread doesn’t increase.

The new remaining counts pass either way, so induction carries this down to the empty suffix, where every count is $0$. $\blacksquare$

So “can this prefix still be completed?” is exactly “do the remaining counts pass?”. That’s the same check I already run on the original string, now applied to what’s left, and it costs $O(26)$.

Observation 3: the greedy is lexicographically smallest¶

At each position, try characters from smallest to largest. Take the first one whose removal leaves remaining counts with $\max - \min \le K$.

By Observation 1, that check covers the suffix starting at the next position. By Observation 2, passing it means a full completion exists. So the greedy never gets stuck, and its output is good.
Any choice smaller than the one taken would fail the check, which means it breaks a suffix immediately. No good string can have that smaller character there after the same prefix. So at the first position where some good string differs from the greedy output, the good string has a larger character, and the greedy output is the lexicographically smallest good string.

If the full counts fail at the start, the answer is $-1$. Otherwise Observation 2 guarantees the loop always finds a character.

Code¶

Up to 26 candidates per position, and each check is an $O(26)$ max/min, so this is $O(26^2 \cdot N)$. Checked against a brute force over all permutations on small random strings.

from collections import Counter


def solve():
    n, k = map(int, input().split())
    s = input()
    freq = Counter()
    for c in s:
        freq[c] += 1

    if max(freq.values()) - min(freq.values()) > k:
        print(-1)
        return

    ans = []
    alpha = sorted(freq.keys())
    for i in range(n):
        for ch in alpha:
            if freq[ch] == 0:
                continue
            freq[ch] -= 1
            # freq is now the suffix after this position; zeros still count towards min.
            if max(freq.values()) - min(freq.values()) <= k:
                ans.append(ch)
                break
            freq[ch] += 1

    print(''.join(ans))


tc = int(input())
for _ in range(tc):
    solve()

The lesson. In “lexicographically smallest arrangement” greedy problems, the hard part is the feasibility check. Look for a cheap condition that is both necessary (it’s one of the constraints) and sufficient: prove it by giving a strategy that keeps it true, here “always place the most frequent character”. Once necessary equals sufficient, the check is just the original condition applied to what’s left.