Counting-based greedy (small alphabet)

32 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

From the letters of abccccdd, using each letter at most as many times as it appears, build the longest palindrome you can. By hand you would start arranging letters: dccaccd reads the same backwards and uses 7 letters. Is 8 possible? You would try moving letters around, and it is not obvious when to stop. For a string of 2,000 letters, arranging by trial is hopeless: there are more arrangements than atoms in the universe.

Build the structure, one piece at a time

The key realisation is that the order of the input letters does not matter at all, only how many of each there are. So the first and only structure is a count table, 26 slots for lowercase and 26 for uppercase, filled by one pass over the string: a → 1, b → 1, c → 4, d → 2.

Now build the answer from the counts, not from the string. A palindrome pairs every letter with its mirror image, except possibly one letter in the exact middle. So each letter contributes its count rounded down to an even number, and if any letter has a count left over, one single letter can sit in the middle.

1. a × 1: 0 pairs, contributes 0; one a left over.
2. b × 1: 0 pairs, contributes 0; one b left over.
3. c × 4: 2 pairs, contributes 4.
4. d × 2: 1 pair, contributes 2.
5. Leftovers exist, so add 1 for the middle. Total 0 + 0 + 4 + 2 + 1 = 7.

The length is 7, and one such palindrome is dccaccd. The algorithm never wrote the palindrome down; it only counted.

Why it is correct

A palindrome of length m has positions k and m − 1 − k holding the same letter, so every letter except the centre (when m is odd) appears an even number of times. Therefore no palindrome can use more than an even number of copies of each letter, plus at most one extra letter in total. That gives an upper bound: the sum of the counts rounded down to even, plus 1 if any count is odd. The construction above reaches that bound: place each pair symmetrically and one leftover in the middle. Upper bound met, so it is the maximum.

length = Σ_letters 2·⌊count/2⌋ + [some count is odd]

Why it is fast

One pass to count is O(n), and the construction loops over at most 52 slots, which is constant: O(n) time, O(1) memory. For 2,000 letters that is about 2,050 steps. Every trial-and-arrangement method is exponential, because it treats the order as information when the order is irrelevant.

How to recognise it in an interview

Cues: a small fixed alphabet (letters, digits, task types), and a question that would be unchanged if the input were shuffled. Say: the order does not matter, so I will count first and reason about the counts. Longest Palindrome is the example. Reorganize String checks that the most frequent letter is at most half the length (rounded up) and then interleaves from the counts. Task Scheduler has the closed form (f − 1)(n + 1) + (number of tasks with the top count), where f is the highest count, again purely from the count table.

02The idea in one line

Count letters/values, then construct the best answer from the counts.

Reach for it when: Longest palindrome, reorganise string, task scheduler math form, string balancing.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Longest Palindrome from 'abccccdd'. These are its captions in order, so you can follow without the video or check a step you missed.

1. Count letters; the answer only depends on the multiset of counts
2. 'a' × 1: 0 pair(s) add 0, one left over
3. 'b' × 1: 0 pair(s) add 0, one left over
4. 'c' × 4: 2 pair(s) add 4
5. 'd' × 2: 1 pair(s) add 2
6. Any one leftover letter can sit in the middle: +1
7. Longest palindrome = 7, e.g. dccaccd
8. One counting pass over a 52-letter alphabet: O(n) time, O(1) space

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Greedy: Furthest reach (jump game), Sort, then take greedily, Reset-on-negative sweep, Last-occurrence partition, Two-pass neighbour constraints, Two-pointer assignment after sorting.