LeetCode 942 · Greedy

DI String Match, explained with a picture

Lining people up from “taller / shorter” notes.

Greedy
▶ Watch it step by step

The problem

Given a string of I (increase) and D (decrease), build any permutation of 0 … n that follows it.

Input:  "IDID"
Output: [0, 4, 1, 3, 2]

Picture it

Picture lining up people of heights 0 … n from notes like “the next one is taller”. For I, use the shortest person left (anyone after them will be taller). For D, use the tallest left. The last person is whoever remains.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Two pointers lo/hi over the values. O(n).

Python solution

def di_string_match(s):
    lo, hi = 0, len(s)
    out = []
    for ch in s:
        if ch == "I":           # next must be taller
            out.append(lo); lo += 1
        else:                   # next must be shorter
            out.append(hi); hi -= 1
    out.append(lo)
    return out

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.