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'.The key idea in #942 DI String Match is to construct a permutation of numbers from 0 to n that follows the pattern described by a string of 'I' (increase) and 'D' (decrease). A common and efficient strategy is a greedy two-pointer approach. Instead of trying every permutation, maintain two boundaries representing the smallest and largest unused numbers.
When the current character in the string is 'I', place the smallest available number and move the lower pointer forward. When the character is 'D', place the largest available number and move the upper pointer backward. This greedy choice guarantees the relative order required by the pattern while ensuring all numbers remain unique.
The process continues for each character in the string, and one number remains for the final position. Because each element is processed once, the algorithm runs efficiently with O(n) time complexity and uses O(n) space for the result array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Two-Pointer Construction | O(n) | O(n) |
NeetCodeIO
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.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), excluding the output array.
1#include <stdio.h>
2#include <stdlib.h>
3
4int* diStringMatch(char * s, int* returnSize){
5 intThis 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.
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.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), discounting the result storage.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like DI String Match appear in interviews at large tech companies because they test greedy thinking and array manipulation. While the exact question may vary, similar pattern-based greedy problems are common in coding interviews.
The optimal approach uses a greedy two-pointer technique. Maintain the smallest and largest available numbers and assign them based on whether the current character is 'I' or 'D'. This ensures the required ordering while processing the string in a single pass.
The greedy strategy works because each 'I' only requires the next value to be larger and each 'D' requires it to be smaller. By always choosing the smallest or largest available number, we satisfy the condition without restricting future placements.
An array or list to store the resulting permutation is sufficient. Along with that, two integer pointers representing the current minimum and maximum available values help implement the greedy strategy efficiently.
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.