Skip to content

What Is Greedy?

The Problem That Reveals Everything

You're given a string s and asked: does "hello" appear as a subsequence?

A subsequence means the letters appear in order, but not necessarily consecutively. They don't need to be adjacent — they just can't appear out of order.

A passing example: s = "hehlollloe". We can pick h at index 0, e at index 1, l at index 3, l at index 5, o at index 8. All in order. Answer: YES.

A failing example: s = "hlelo". We find h at 0, but the e doesn't appear until index 2 — by which point the first l (index 1) is already behind us. There's only one l remaining after the e. We can match h, e, l, but there's no second l after that. Answer: NO.

The algorithm writes itself: scan left to right, match each character of "hello" to the first available occurrence. But here's the question that matters — when should you not take a match immediately?

The Greedy Choice: Always Take the Earliest Match

When you find a character that fits the next letter you need, should you take it?

Yes. Always.

Early match leaves a larger search window — taking position i gives more room than waiting for position k

Suppose you're looking for e, and you see it at position i. You could skip it, hoping to find an e at some better position k > i. But what's better about position k? It's strictly further right. If you take position i, you start searching for l from position i+1. If you take position k, you start from k+1. The window [i+1, n-1] is strictly larger than [k+1, n-1].

A larger search window never hurts. Any sequence of matches you could find starting from k+1 you can also find starting from i+1 (since i+1 ≤ k+1). There is zero benefit to delaying a match.

This is the essence of greedy: the locally best action (take the match now) is globally optimal because it strictly dominates any alternative.

The Trap: What If You Skip?

Consider s = "hlelo", target = "hello".

Greedy (always take earliest):

i s[i] Looking for Match? j
0 h h ✓ 1
1 l e ✗ 1
2 e e ✓ 2
3 l l ✓ 3
4 o l ✗ 3

j = 3 at the end. We matched h, e, l — but couldn't find the second l or o. Answer: NO.

Could we have done better? The full string h,l,e,l,o contains exactly one h, one e, two ls, one o. For "hello" we need h,e,l,l,o in order. The h is at 0, e at 2, first l at 1... but that's before e. The second l is at 3, o at 4. To match in order: h(0), e(2), l(3), l(?)... there's no second l after position 3. Answer is genuinely NO. Greedy is correct.

The "trap" is thinking you could be smarter by skipping. You can't.

Tracing the Full Algorithm

Let's trace on s = "hehlollloe", target = "hello":

i s[i] j Looking for Match? j after
0 h 0 h ✓ 1
1 e 1 e ✓ 2
2 h 2 l ✗ 2
3 l 2 l ✓ 3
4 o 3 l ✗ 3
5 l 3 l ✓ 4
6 l 4 o ✗ 4
7 l 4 o ✗ 4
8 o 4 o ✓ 5
9 e — done — —

j = 5 = target.size(). Answer: YES.

j only ever increases. Each character of "hello" is matched once, to its first available occurrence. One left-to-right pass: O(|s|).

Why This Is a Greedy Algorithm

A greedy algorithm builds a solution by making locally optimal choices, one at a time, without exhaustive search. In the simplest form — like this subsequence match — the choices are irrevocable: once you match h at position i, you don't go back and unmatch it.

The greedy choice at each step never prevents an optimal outcome.

Matching earlier leaves at least as much room for future matches as matching later. This "never hurts" property is what separates problems where greedy works from problems where it doesn't (we'll see failures in Lesson 3).

Not all greedy algorithms are permanently irrevocable. In later chapters, you'll learn greedy with undo — a technique where the algorithm makes a provisional choice, leaves a mathematical "breadcrumb," and can reverse the decision later if a better option appears. The greedy spirit is the same (always pick the locally best option), but the mechanism is more sophisticated.

Greedy algorithms you already know. If you've studied graph algorithms, you've already used greedy without realizing it. Dijkstra's shortest path algorithm is greedy: always extend the nearest unvisited node. Prim's and Kruskal's algorithms for Minimum Spanning Trees are greedy: always pick the cheapest edge that doesn't create a cycle. These work because the underlying structures (shortest-path substructure, matroid property of forests) guarantee that local choices are globally optimal. This course teaches you to recognize and prove that same guarantee in new settings.

Example 2: HR Halloween Party — Greedy via Math

The subsequence problem was greedy on a sequence — scanning, making irrevocable choices about characters. But the greedy mindset applies far beyond arrays and strings. It shows up whenever you need to distribute a limited resource to maximize some product, and the locally balanced choice turns out to be globally optimal.

You cut a chocolate bar on an infinite 2D grid. With exactly k cuts, maximize \(1 \times 1\) pieces. Each cut is a straight horizontal or vertical line splitting one piece.

Let \(h\) = horizontal cuts, \(v\) = vertical cuts, \(h + v = k\). The number of rows after \(h\) cuts = \(h + 1\). The number of columns = \(v + 1\). Total pieces = \((h+1)(v+1)\).

The greedy question: how to split \(k\) cuts between horizontal and vertical?

You want to maximize \((h+1)(v+1)\) subject to \(h + v = k\), where \(h, v \geq 0\).

Let \(a = h+1\) and \(b = v+1\). Then \(a + b = k + 2\), and you want to maximize \(a \times b\).

For a fixed sum, the product is maximized when the two factors are as equal as possible. This follows from the AM-GM inequality: \((a+b)^2/4 \geq ab\), with equality when \(a = b\).

So: \(h = \lfloor k/2 \rfloor\), \(v = \lceil k/2 \rceil\). Total pieces:

\[\text{pieces} = \left(\lfloor k/2 \rfloor + 1\right) \times \left(\lceil k/2 \rceil + 1\right)\]

The exchange argument (why rebalancing always helps):

Suppose the split is unbalanced: \(h + 1 > v + 1 + 1\), i.e., horizontal has at least 2 more rows than vertical has columns. Move one cut from horizontal to vertical. The product changes from \((h+1)(v+1)\) to \(h(v+2)\).

  • Before the swap: \((h+1)(v+1)\)
  • After the swap: \(h(v+2) = hv + 2h\)
  • Difference: \(h(v+2) - (h+1)(v+1) = hv + 2h - hv - h - v - 1 = h - v - 1\)
  • Since \(h > v + 1\), the difference \(h - v - 1 > 0\)

Rebalancing strictly increases the product. Repeating this argument: the greedy "split as evenly as possible" is optimal.

k h v Pieces
1 0 1 1×2=2
2 1 1 2×2=4
3 1 2 2×3=6
4 2 2 3×3=9
5 2 3 3×4=12
6 3 3 4×4=16

What Makes a Problem "Greedy"

Three properties you're looking for:

  1. No regret: the greedy choice is never invalidated by future choices.
  2. Optimal substructure: after making your greedy choice, the problem that remains is just a smaller version of the exact same problem. For the subsequence match: once you've matched h, the remaining problem is "does ello appear as a subsequence of the rest of the string?" — same structure, smaller input.
  3. Proof exists: either exchange argument or greedy-stays-ahead induction confirms the choice.

When property 1 breaks down — when a locally good choice blocks two globally better choices — greedy fails. Lesson 3 shows exactly this.

The Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;

    string target = "hello";
    int j = 0;
    for (int i = 0; i < (int)s.size() && j < 5; i++) {
        if (s[i] == target[j]) j++;
    }

    cout << (j == 5 ? "YES" : "NO") << "\n";
    return 0;
}

Three things to notice: - j only advances, never retreats. Irrevocable decisions in code. - Early exit j < 5. Once all characters matched, stop scanning. - O(|s|) time. One pass, no backtracking.

Try It

The starter code has a TODO where j++ should go. Fill it in.

Input: hello
Output: YES

Input: world
Output: NO

Input: heello
Output: YES

Input: helo
Output: NO

Trace "helo" by hand: match h, e, l — need another l before o. Only one l exists. NO is correct.

Predict before running: For s = "hheeelllllo", what's the answer? Trace through manually first.

Challenge: What if the target were "heel"? Modify target to "heel" and test on s = "heelo". What does the greedy do, and is it correct?

Problems

Problem Link Difficulty
CF58A — Chat Room codeforces.com/problemset/problem/58/A 1000
HR — Halloween Party hackerrank.com/challenges/halloween-party Easy