Dynamic Programming, Greedy, And Combinatorial Optimization

What's being tested

These problems test recognizing when a seemingly exponential schedule or string constraint decomposes into dynamic programming, greedy exchange arguments, or equivalence classes. You must define states precisely, account for global constraints such as palindrome symmetry and periodicity, and justify why local choices are safe. Interviewers also probe boundary handling, complexity, and whether your implementation matches the stated function contract.

Patterns & templates

• State-machine DP for schedules: track day index, consecutive-work streak, and conversions used; transition work/off in O(nk) or O(nkL) depending on streak handling.

• Greedy interval selection: when bonuses depend only on runs, compare converting an off-day gap versus extending or merging working blocks; compute each gain before choosing.

• Palindrome pair counting: mismatched mirrored characters contribute one change; for blocks, precompute costs with cost[l][r] or expand around centers.

• Disjoint equivalence classes for k-periodic palindromes: union indices related by i ≡ j (mod k) and reflection; each component takes its majority character.

• Union-find or canonical representatives compress global character constraints; total work is near-linear, O(n α(n)), after generating all index relations.

• MEX reasoning requires checking presence of every value below the candidate and the effect of the single bounded increment; never increment a value to n.

• Production-quality implementation validates k, empty inputs, k > n, zero conversions, and integer ranges; state complexity should be stated explicitly.

Common pitfalls

Pitfall: Assuming every bonus problem is greedy; overlapping run effects often require DP because an early conversion changes multiple future transitions.

Pitfall: Counting mismatched positions independently when periodicity links them globally; first build the complete constraint component.

Pitfall: Forgetting that “at most” permits using fewer than k operations, especially when conversions can reduce or fail to increase earnings.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.