❓ The question first
❓ THE QUESTION
Problem — Arranging Books
A shelf holds books of three sizes: L (large), M (medium), S (small). Valentina wants all the L books first, then all the M books, then all the S books. One swap exchanges any two books. What is the fewest number of swaps needed?
Input
One line: a string of L, M, S characters — the shelf from left to right.
LLSLM
Output
One integer: the minimum number of swaps.
2
🎬 The solution, step by step
The idea — count zones, never simulate:
- Count how many L, M, S exist. That fixes the three zones of the finished shelf.
- Count the misplaced books in each zone (an S sitting in the L-zone, etc.).
- Direct pairs (two books belonging in each other's zones) fix 2 books per swap → cost 1 each. What's left always forms 3-cycles → cost 2 each.
Animation — walk the official sample
💻 The code
s = input().strip()
count = {ch: s.count(ch) for ch in "LMS"}
zone = {} # where each zone starts/ends
start = 0
for ch in "LMS":
zone[ch] = (start, start + count[ch])
start += count[ch]
mis = {z: {c: 0 for c in "LMS"} for z in "LMS"}
for z in "LMS": # count wrong books per zone
a, b = zone[z]
for ch in s[a:b]:
mis[z][ch] += 1
direct = (min(mis['L']['M'], mis['M']['L'])
+ min(mis['L']['S'], mis['S']['L'])
+ min(mis['M']['S'], mis['S']['M']))
misplaced = sum(mis[z][c] for z in "LMS" for c in "LMS" if z != c)
cycles = (misplaced - 2 * direct) // 3
print(direct + 2 * cycles) # direct pairs: 1 each; 3-cycles: 2 each
⭐ Key points & traps
Trap — actually swapping: simulating swaps (bubble sort style) counts YOUR swaps, not the minimum. The contest asks for the fewest possible, which is a counting question: zones → misplaced → pairs and cycles.
Why a 3-cycle costs exactly 2: swap any two of the three — one lands correctly, the other two now form a direct pair — swap them. 2 total, and 1 is impossible because a single swap can put at most 2 books right, and in a cycle no single swap puts ANY book in its own zone… check Step 4's shelf if that feels surprising.
Edge cases: a shelf may contain no M's at all (two zones only) — the counting still works, the M-zone is just empty. Sample 1 (
LMMMS) has zero misplaced books → 0.✋ Your turn — predict first, then check
Shelf SML — minimum swaps?
Zones are one book each. S sits in the L-zone and L sits in the S-zone: a direct pair → 1 swap. Answer: 1.