Introduction

The editorial for this problem offers two approaches: a min/max table range tracker and a binary-search-over-ambiverts solution. This blog presents a third, independently derived O(n) greedy that feels more intuitive — at least to me. The central idea is tracking floating ambiverts: ambiverts who sat down in an already-occupied table but haven't been committed to a specific role yet, and can retroactively "become" introverts to rescue a future extrovert.

Key observation

An extrovert needs a non-empty table. An introvert needs a completely empty table. An ambivert can do either. The tricky part is the order of decisions: we can't look ahead, so we must make lazy commitments.

Core insight

When an ambivert sits at an already-occupied table (acting like an extrovert), we don't need to commit them yet. If a later extrovert arrives with no free seat, we can retroactively declare one of those ambiverts an introvert — opening a fresh empty table for them — and hand the seat they freed to the extrovert. This "retroactive role assignment" is always safe.

Variables

unoccupied -> Number of completely empty tables. Starts at x. rem -> Total empty seats across all occupied tables (i.e. tables with ≥ 1 person seated). ct -> Count of "floating" ambiverts — ambiverts currently occupying a seat in an occupied table but not yet committed as introverts. ans -> Number of people kicked out. Final answer = n − ans.

The greedy — case by case

Introvert (I)

• If unoccupied > 0: seat them at a fresh table. unoccupied--, rem += (s−1).
• Otherwise: no empty table exists, kick them out. ans++.

Ambivert (A)

• If rem > 0: sit them in the occupied table, rem--, mark as floating: ct++.
• If rem == 0 and unoccupied > 0: treat as introvert — open a new table. unoccupied--, rem += (s−1).
• If both are 0: no seat anywhere, kick out. ans++.

Extrovert (E)

• If rem > 0: a seat exists in an occupied table. Seat them, rem--.
• If rem == 0 but ct > 0 and unoccupied > 0: redeem a floating ambivert as an introvert. That ambivert "moves" to a fresh empty table (unoccupied--, ct--), freeing their old seat which this extrovert takes. Net effect: rem += (s−1) and then the extrovert uses one of those seats: so effectively rem += (s−2)... but in code we do ct--; unoccupied--; rem += (s−1); and the extrovert consumes one seat from rem — see code below for the exact order.
• Otherwise: kick them out. ans++.

The ambivert case with rem > 0 always prefers sitting in an occupied table and becoming floating. This is strictly better than opening a new table, because it preserves empty tables for future introverts and stays reversible.

Worked example

Test case 1: n=5, x=2, s=2, u = "EIAIE". Initial state: unoccupied=2, rem=0, ct=0, ans=0. i char action unocc. rem ct ans

0 E rem=0, ct=0 → kick out 2 0 0 1
1 I unoccupied>0 → open table 1 1 1 0 1
2 A rem>0 → sit in table 1, float 1 0 1 1
3 I unoccupied>0 → open table 2 0 1 1 1
4 E rem>0 → sit in table 2 0 0 1 1

Answer: n − ans = 5 − 1 = 4. Matches expected output.

Why this is correct

The greedy never makes a strictly wrong decision:

Ambiverts prefer occupied tables when available. If we instead opened a new table eagerly, we'd block future introverts unnecessarily. Sitting in an occupied table costs nothing and stays reversible.

Floating ambiverts can always be redeemed. A floating ambivert sits at table T (occupied). When redeemed, they move to a fresh table T' and the extrovert takes their old seat at T. The extrovert's constraint (non-empty table) is still satisfied since T still has its original occupants. The ambivert's constraint is also satisfied since T' was empty before they arrived.

Order of redemption doesn't matter. We only track the count ct, not which specific ambivert is redeemed. Since all floating ambiverts are equivalent in their role, any one of them can be chosen — the answer is the same.

This is the link of solution

Complexity

Time

O(n) per test case — single linear pass, O(1) work per character.

Space

O(1) extra — only four integer variables beyond the input string.