DI String Match - Video Solutions

Problem Overview: You receive a string s consisting of characters 'I' (increase) and 'D' (decrease). Build a permutation of integers from 0 to n such that every adjacent pair follows the rule defined by the string. If s[i] = 'I', then perm[i] < perm[i+1]. If s[i] = 'D', then perm[i] > perm[i+1]. The task is to return any valid permutation.

Approach 1: Two-Pointer Technique (O(n) time, O(1) space)

This method uses two pointers that represent the smallest and largest numbers still available in the permutation. Initialize low = 0 and high = n. Iterate through the string and decide which value to place next. When you see 'I', place low in the result and increment it. When you see 'D', place high and decrement it. The logic works because an increasing constraint requires the smallest remaining value, while a decreasing constraint requires the largest. After processing all characters, one number remains between low and high; append it to finish the permutation.

The key insight is that each decision only affects the current pair, so you don't need to look ahead or rearrange previous elements. Maintaining the remaining number range with two pointers guarantees every constraint is satisfied. The algorithm scans the string once and performs constant-time assignments, giving O(n) time and O(1) extra space. This approach heavily relies on the Two Pointers pattern combined with simple Greedy decisions.

Approach 2: Greedy Character Matching (O(n) time, O(1) space)

The greedy perspective focuses on satisfying each character constraint immediately using the best available number. Maintain a valid numeric range [low, high]. For each character in the String, choose a number that guarantees the inequality with the next element. If the current character is 'I', choose the smallest unused number so the next value can still be larger. If it is 'D', choose the largest unused number so the next value can still be smaller.

This greedy choice works because using extreme values preserves flexibility for the remaining sequence. Selecting a middle value could break a future constraint, but choosing from the boundaries always leaves a valid interval for the rest of the permutation. Each step shrinks the available range by one, so the algorithm processes the input in a single pass. The result is again O(n) time and O(1) auxiliary space while producing a valid permutation without backtracking.

Recommended for interviews: The two-pointer greedy approach is what interviewers expect. It demonstrates that you recognize the permutation range trick and can translate inequality constraints directly into pointer movement. Brute force permutation generation would be factorial time and impractical. Showing the greedy insight and explaining why extreme values preserve future flexibility signals strong problem-solving skills.