You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.
A 0-indexed string num of length n + 1 is created using the following conditions:
num consists of the digits '1' to '9', where each digit is used at most once.pattern[i] == 'I', then num[i] < num[i + 1].pattern[i] == 'D', then num[i] > num[i + 1].Return the lexicographically smallest possible string num that meets the conditions.
Example 1:
Input: pattern = "IIIDIDDD" Output: "123549876" Explanation: At indices 0, 1, 2, and 4 we must have that num[i] < num[i+1]. At indices 3, 5, 6, and 7 we must have that num[i] > num[i+1]. Some possible values of num are "245639871", "135749862", and "123849765". It can be proven that "123549876" is the smallest possible num that meets the conditions. Note that "123414321" is not possible because the digit '1' is used more than once.
Example 2:
Input: pattern = "DDD" Output: "4321" Explanation: Some possible values of num are "9876", "7321", and "8742". It can be proven that "4321" is the smallest possible num that meets the conditions.
Constraints:
1 <= pattern.length <= 8pattern consists of only the letters 'I' and 'D'.This approach utilizes a stack to construct the number by handling 'I' and 'D' separately. For 'D', we keep adding digits to the stack and for 'I' we release them in reverse order which satisfies the 'D' requirement.
This Python code initiates a result string res and a stack. It iterates over the pattern plus one additional iteration. In each iteration, the next available number is pushed to the stack. When an 'I' or the end of the pattern is reached, the stack is popped to res to fulfill 'D' sequences by reversing the additions.
Java
C++
C
C#
JavaScript
Time Complexity: O(n) - where n is the length of the pattern because each element is pushed and popped once.
Space Complexity: O(n) - due to stack storage as needed during computation.
In this approach, we use two pointers and direct calculation of segments using 'D' marks to populate numbers into the result. We fill numbers in reverse order whenever a 'D' is encountered.
This solution adds numbers sequentially and reverses segments during 'I'. At each occurrence of 'I', it reverses the segment from the last 'I' or the start, ensuring minimal lexicographical order through efficient list slicing and reversing.
Java
C++
C
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n) - storing numbers progressively.
| Approach | Complexity |
|---|---|
| Greedy Approach with Stack | Time Complexity: O(n) - where n is the length of the pattern because each element is pushed and popped once. |
| Construct from Left to Right | Time Complexity: O(n) |
Construct Smallest Number From DI String - Leetcode 2375 - Python • NeetCodeIO • 10,421 views views
Watch 9 more video solutions →Practice Construct Smallest Number From DI String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor