A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:
s[i] == 'I' if perm[i] < perm[i + 1], ands[i] == 'D' if perm[i] > perm[i + 1].Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.
Example 1:
Input: s = "IDID" Output: [0,4,1,3,2]
Example 2:
Input: s = "III" Output: [0,1,2,3]
Example 3:
Input: s = "DDI" Output: [3,2,0,1]
Constraints:
1 <= s.length <= 105s[i] is either 'I' or 'D'.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.
Description: Use two pointers, or indices - one starting at 0 and the other at 'n'. For each 'I' in the string, assign the lowest available number and increment the 'low' index. For each 'D', assign the highest available number and decrement the 'high' index. This approach efficiently fills the permutation array by maximizing the immediate decision at each step.
This C solution uses a two-pointer approach. It initializes 'low' and 'high' to track the currently available smallest and largest numbers. As it iterates through the string 's', it assigns numbers based on whether 'I' or 'D' is encountered, thereby constructing the permutation.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), excluding the output array.
Description: The Greedy Character Matching approach involves tracking two dynamic bounds, 'low' and 'high', to determine at every step what the current optimal choice for our permutation should be. By iterating over the string 's', for every 'I', append the current lowest available integer and increment it. For 'D', add the current highest integer and decrement it, ensuring the correct permutation ordering through direct engagement with the constraints.
This C implementation captures the essence of greedy processing by dynamically adjusting 'low' and 'high'. It leverages pointer manipulation for assignments and appends the last remaining 'low' to complete the permutation.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), discounting the result storage.
We can use two pointers low and high to represent the current minimum and maximum values, respectively. Then, we traverse the string s. If the current character is I, we add low to the result array, and increment low by 1; if the current character is D, we add high to the result array, and decrement high by 1.
Finally, we add low to the result array and return the result array.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n), where n is the length of the string. |
| Greedy Character Matching | Time Complexity: O(n), where n is the length of the string. |
| Greedy Algorithm | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n) | O(1) | Best general solution. Efficient single-pass construction using low/high bounds. |
| Greedy Character Matching | O(n) | O(1) | Useful when reasoning about inequality constraints and greedy selection. |
942 DI String Match | Easy Level Question| Leetcode Easy Level Questions Complete Playlist in Python • EduEverybody • 1,297 views views
Watch 9 more video solutions →Practice DI String Match with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor