DI String Match

DI String Match

What is this problem about?

The DI String Match coding problem gives you a string s containing only 'I' (Increase) and 'D' (Decrease). You need to return an array of integers [0, 1, ..., n] such that for every index $i$:

• If $s[i] == 'I'$, $arr[i] < arr[i+1]$.
• If $s[i] == 'D'$, $arr[i] > arr[i+1]$.

Why is this asked in interviews?

Amazon and Google use this "Easy" problem to test your ability to apply greedy logic to range-based constraints. It’s a test of "Range Contraction." It evaluations whether you can see that using the extremes of the available numbers (0 and $n$) for 'I' and 'D' respectively satisfies the requirements perfectly.

Algorithmic pattern used

This problem uses the Two Pointers interview pattern and Greedy approach.

1. Maintain two pointers: low = 0 and high = n.
2. Iterate through the string:
   • If 'I', pick low and increment it.
   • If 'D', pick high and decrement it.
3. The last number in the array will be the final value of low (which will equal high).

Example explanation

String: "IDID", $n=4$. Available: [0, 1, 2, 3, 4].

1. 'I': Pick 0. low=1. Array: [0].
2. 'D': Pick 4. high=3. Array: [0, 4].
3. 'I': Pick 1. low=2. Array: [0, 4, 1].
4. 'D': Pick 3. high=2. Array: [0, 4, 1, 3].
5. End: Add remaining 2. Result: [0, 4, 1, 3, 2].

Common mistakes candidates make

• Backtracking: Trying to use a complex search to find a valid permutation, which is $O(N!)$.
• Complexity: Overthinking the relationship between distant indices. The greedy approach works because using the smallest available number for 'I' guarantees that any subsequent number will be larger.
• Off-by-one: Forgetting to add the final number after the loop through the string finishes.

Interview preparation tip

The "Two Pointers at the extremes" trick is a common way to solve construction problems involving "Increasing" and "Decreasing" constraints. It ensures that you never "run out" of room to make the next move.