Graph Real-Life Problems

What is this?

Two problems that start as graph questions and finish somewhere else. Smallest String With Swaps uses union-find to discover which positions can reach each other, and then the answer is a sort. Campus Bikes II looks like a matching problem with an easy greedy and is really a bitmask DP, because the greedy is wrong.

Both are about what comes after you have the structure.

💡 Fun fact: the greedy for Campus Bikes II — repeatedly take the closest remaining worker–bike pair — is not merely unproven, it is provably wrong on four points. Put workers at (0,0) and (0,2), bikes at (0,1) and (1,0). The greedy grabs the (0,0) ↔ (0,1) pair at cost 1 and strands the second worker with a cost-3 ride, total 4. Assigning (0,0) to the farther-looking bike gives 1 + 1 = 2. That greedy is the correct answer to a different problem — Campus Bikes I, which asks for exactly that pairing rule rather than the minimum total.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: connectivity tells you what is possible; a second technique — a sort, or a DP over subsets — picks the best among the possibilities. Stopping at the graph gives you half a solution.

1. Connectivity, then a sort

The insight is that the given pairs are not the only swaps available. Chaining them means any permutation within a connected component is reachable, so each component's characters can be arranged freely:

for a, b in pairs: union(a, b)

groups = defaultdict(list)
for i in range(len(s)): groups[find(i)].append(i)

out = list(s)
for idxs in groups.values():
    for i, ch in zip(sorted(idxs), sorted(out[i] for i in idxs)):
        out[i] = ch                          # smallest char at the smallest index

Sorting the indices and the characters separately, then zipping them, is what makes the result lexicographically smallest: within a component the earliest position gets the smallest available character. Positions in no pair form singleton components and are left alone by the same code — no special case.

2. When the greedy fails, enumerate the subsets

dp = [inf] * (1 << m); dp[0] = 0
for mask in range(1 << m):
    if dp[mask] == inf: continue
    w = popcount(mask)                       # ← the worker to assign next
    if w == n: continue
    for b in range(m):
        if not mask >> b & 1:
            dp[mask | 1 << b] = min(dp[mask | 1 << b], dp[mask] + dist(workers[w], bikes[b]))
return min(dp[mask] for mask in range(1 << m) if popcount(mask) == n)

The trick that removes a whole DP dimension: the number of bits set in the mask is the index of the next worker. Workers are assigned in order, so "which bikes are taken" already determines "how many workers are done". One dimension instead of two, and the cost is O(2^m × m) — fine because m ≤ 10.

Naming why the greedy fails is worth as much here as the DP itself.

3. A 30-second worked example (swaps)

s = "dcab", pairs = [[0,3], [1,2]]

union(0,3)  →  component {0, 3}     characters  'd', 'b'
union(1,2)  →  component {1, 2}     characters  'c', 'a'

component {0,3}:  indices sorted [0,3], chars sorted ['b','d']
                  → position 0 = 'b',  position 3 = 'd'
component {1,2}:  indices sorted [1,2], chars sorted ['a','c']
                  → position 1 = 'a',  position 2 = 'c'

result: "bacd"

Add the single pair [0,2] and everything merges into one component — all four characters can then be arranged freely, and the answer improves to "abcd". One extra edge, a completely different result, and not a line of the algorithm changes.

4. Where you'll actually meet this

• Ride-hailing and delivery dispatch. Assigning drivers to requests at minimum total distance is Campus Bikes II at production scale.
• Task and shift assignment. Matching people to jobs by cost, where the locally cheapest choice is routinely not globally optimal.
• Data reconciliation. Records grouped by transitive matching rules, then normalised within each group.
• Anagram and permutation constraints. Any "these positions may be rearranged among themselves" rule is a component sort.
• Resource allocation. Small-n assignment problems where an exact answer beats a heuristic and a bitmask fits.

5. Problems in this chapter

▶ Smallest String With Swaps

Lexicographically smallest string reachable by repeated swaps. Union the paired indices, then sort characters within each component into its sorted positions.
Pattern: union-find + per-component sort. Target: O(n log n) time, O(n) space.

▶ Campus Bikes II

Assign each worker a distinct bike minimising total Manhattan distance. DP over the set of used bikes, with the popcount naming the next worker.
Pattern: bitmask DP over subsets. Target: O(2^m × m) time, O(2^m) space.

6. Common pitfalls 🚫

• Only swapping the listed pairs. Swaps compose, so the reachable set is the whole connected component.
• Sorting the whole string. Only positions inside one component may be permuted.
• Reusing the nearest-pair greedy from Campus Bikes I. Different question, and there is a four-point counterexample.
• Adding a worker dimension to the DP. The popcount of the mask already says which worker is next.
• Iterating masks out of order. Ascending order guarantees every predecessor state is final before it is read.
• Reading the answer from dp[full]. With m > n the answer is the best mask with exactly n bits set.
• Forgetting singleton components — they need no special handling, but only if the grouping includes every index.

7. Key takeaways

1. Connectivity establishes what is possible; a second step chooses the best of it.
2. Swaps compose, which turns a pair list into components and the problem into a sort.
3. Smallest character at the smallest index, per component, is the whole lexicographic argument.
4. A plausible greedy needs a counterexample or a proof — and here the counterexample is four points.
5. A subset mask can encode two things at once. Its popcount removes an entire DP dimension.
6. Small constraints are a hint. m ≤ 10 is the interviewer telling you 2^m is acceptable.
7. Why interviewers like it: both problems punish stopping at the first idea, and reward saying why it fails.

Order: Smallest String With Swaps → Campus Bikes II.