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'.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), discounting the result storage.
| 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. |
String Matching in an Array - Leetcode 1408 - Python • NeetCodeIO • 10,849 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