DI String Match: Greedy Two-Pointer Construction

May 25, 20267 min read

leetcodeproblemeasyarraysmathgreedy

Given a string s of length n containing only the characters 'I' (increasing) and 'D' (decreasing), find any permutation perm of [0, 1, ..., n] such that for every index i: if s[i] == 'I', then perm[i] < perm[i+1], and if s[i] == 'D', then perm[i] > perm[i+1].

This is LeetCode 942: DI String Match, an easy problem that introduces the greedy two-pointer construction pattern. The key idea is that you can build a valid permutation in a single pass by assigning the smallest available number for 'I' and the largest available number for 'D'.

s = "IDID", n = 4. Green = I (increasing), red = D (decreasing). The permutation [0, 4, 1, 3, 2] satisfies every constraint: 0 < 4, 4 > 1, 1 < 3, 3 > 2.

Why this problem matters

DI String Match teaches you how to translate ordering constraints into a construction strategy. Instead of trying permutations and checking which ones satisfy the constraints, you learn to build the answer directly by reasoning about what each constraint requires. This "construct, don't search" mindset is essential for greedy problems.

The two-pointer technique used here also shows up in problems like Sort Colors and Partition Labels, where you maintain boundaries from both ends and converge toward the middle. Once you internalize this pattern, you can apply it to any problem where you need to assign values from a range while satisfying local ordering rules.

The brute force approach

A brute force solution would generate all permutations of [0, 1, ..., n] and check each one against the DI string. For every permutation, you verify that each adjacent pair satisfies the corresponding 'I' or 'D' constraint.

from itertools import permutations

def di_string_match_brute(s):
    n = len(s)
    for perm in permutations(range(n + 1)):
        valid = True
        for i in range(n):
            if s[i] == "I" and perm[i] >= perm[i + 1]:
                valid = False
                break
            if s[i] == "D" and perm[i] <= perm[i + 1]:
                valid = False
                break
        if valid:
            return list(perm)

This works but runs in O((n+1)!) time, which is unusable for any input beyond about 10 characters. With n up to 10,000 in the problem constraints, you need something far more efficient.

The key insight: greedy two-pointer construction

Think about what each character in the DI string is really asking for. When you see 'I' at position i, you need perm[i] < perm[i+1]. The safest way to guarantee this is to place the smallest number still available at position i. No matter what comes next, there will always be a larger number available for position i+1.

The same logic works in reverse. When you see 'D', place the largest number still available. That guarantees the next position can hold something smaller.

Maintain two pointers: low starting at 0 and high starting at n. For each 'I', assign low and increment it. For each 'D', assign high and decrement it. After processing all characters, low and high will be equal, and you append that final value.

Why does this always work? Because each assignment uses a value from one end of the remaining range. After placing low for an 'I', every unused number is strictly larger, so the next value will be greater regardless of what it is. After placing high for a 'D', every unused number is strictly smaller. The constraints are satisfied by construction.

Walking through it step by step

Let's trace through s = "IDID" with n = 4. We need a permutation of [0, 1, 2, 3, 4]. We start with low = 0 and high = 4.

Step 1: s[0] = 'I', use low = 0, then low becomes 1

s[0] is 'I', so we want the smallest available number. Place low (0) and increment low to 1.

Step 2: s[1] = 'D', use high = 4, then high becomes 3

s[1] is 'D', so we want the largest available number. Place high (4) and decrement high to 3.

Step 3: s[2] = 'I', use low = 1, then low becomes 2

s[2] is 'I', so place low (1) and increment low to 2. Notice 4 > 1 satisfied the previous 'D'.

Step 4: s[3] = 'D', use high = 3, then high becomes 2

s[3] is 'D', so place high (3) and decrement high to 2. Now low and high have converged.

Step 5: low == high == 2, append the last remaining value

One number remains: 2. Append it. Final permutation [0, 4, 1, 3, 2] satisfies all constraints. Done.

Every constraint is satisfied: 0 < 4 (I), 4 > 1 (D), 1 < 3 (I), 3 > 2 (D). The two pointers converged at 2, which became the final element.

Practice this problem with spaced repetition

The greedy solution

def diStringMatch(s):
    n = len(s)
    low, high = 0, n
    perm = []
    for ch in s:
        if ch == "I":
            perm.append(low)
            low += 1
        else:
            perm.append(high)
            high -= 1
    perm.append(low)
    return perm

Two pointers, one loop. Here is what each piece does:

low starts at 0 and high starts at n. These track the smallest and largest unused values in the range [0, n].
For each character in s, assign from the appropriate end. 'I' takes from low (guaranteeing the next value is larger). 'D' takes from high (guaranteeing the next value is smaller).
After the loop, one value remains (low == high). Append it to complete the permutation.
The result has n + 1 elements, which is exactly the size of a permutation of [0, 1, ..., n].

Complexity analysis

Metric	Value
Time	O(n), single pass through the string
Space	O(n), for the result array

This is optimal. You must read each character of s at least once, so O(n) time is the lower bound. The output itself requires O(n) space, so you cannot do better.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Greedy construction from constraints

The pattern of building an output directly from constraint rules instead of searching through candidates:

for constraint in constraints:
    if constraint requires "increasing":
        assign_smallest_available()
    else:
        assign_largest_available()

In DI String Match, the constraint is the I/D character. In problems like Smallest String With Swaps, you also build the answer greedily by assigning values from a sorted pool. The skeleton is the same: read a constraint, pick the optimal value, move on.

2. Two-pointer range consumption

The pattern of maintaining two pointers at opposite ends of a value range and consuming from either end:

low, high = 0, n
for item in sequence:
    if condition(item):
        use(low)
        low += 1
    else:
        use(high)
        high -= 1

In DI String Match, low and high track the remaining range of unused values. In Sort Colors (Dutch National Flag), two pointers track the boundaries of the 0-region and 2-region. In Container With Most Water, two pointers squeeze inward from both ends. The core idea is the same: converge from both sides based on local decisions.

The greedy approach works here because each local decision (assign from low or high) never conflicts with future decisions. Every unused number after a low assignment is strictly larger, and every unused number after a high assignment is strictly smaller. This guarantee is what makes the greedy choice provably correct.

Edge cases

Before submitting, make sure your solution handles these:

All I's "IIII": low increments from 0 to 4, producing [0, 1, 2, 3, 4]. A simple ascending sequence.
All D's "DDDD": high decrements from 4 to 0, producing [4, 3, 2, 1, 0]. A simple descending sequence.
Single character "I" or "D": produces [0, 1] or [1, 0]. The smallest valid cases.
Alternating "IDID": the traced example above, producing [0, 4, 1, 3, 2].
Long runs "IIIDDD": ascending prefix [0, 1, 2, 3] followed by descending suffix starting from high. The pointers converge in the middle.
Length 1 string with n = 1: permutation of [0, 1], only two possible outputs.

The greedy solution handles all of these without special-case logic.

Build your pattern library with CodeBricks

Common mistakes

1. Forgetting to append the final element. After the loop, one number remains (where low == high). If you forget to append it, the output has n elements instead of n + 1, and it is not a valid permutation.

2. Confusing when to use low vs high. Some people assign high for 'I' and low for 'D', which reverses the logic. Remember: 'I' means "go up next," so use the smallest available now. 'D' means "go down next," so use the largest available now.

3. Off-by-one on the initial high value. The permutation covers [0, n], not [0, n-1]. If s has length n, then high should start at n, not n - 1. Starting at n - 1 means you never use the value n and use some value twice.

4. Returning the wrong type. The problem asks for a list of integers. Make sure you are not returning a string or tuple. In Python, perm.append() builds a list, so this is handled naturally.

From understanding to recall

You have read the greedy solution and it makes sense. Two pointers, one loop, assign from the correct end. Clean. But can you write it from scratch in an interview without looking at it?

The details matter: initializing high to n (not n - 1), appending low (not high) at the end, and remembering that both values are the same at that point. These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the two-pointer construction loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "build a permutation satisfying ordering constraints" and the code flows out without hesitation.

The greedy two-pointer construction pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Jump Game - Another greedy problem where a simple local rule replaces brute-force simulation
Two Sum - Two-pointer technique for searching within a value range
Sort Colors - Two-pointer array construction with boundary convergence

CodeBricks breaks the DI string match LeetCode problem into its greedy construction and two-pointer building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a constraint-based permutation question shows up in your interview, you do not think about it. You just write it.

Try CodeBricks free