Leetcode 2375: Construct Smallest Number From DI String
You are given a string
pattern consisting of the characters ‘I’ and ‘D’, where ‘I’ indicates that the next number in a sequence should be greater, and ‘D’ means the next number should be smaller. You need to construct the lexicographically smallest string num of length n + 1 such that the digits in num follow the conditions set by the pattern. The digits in num must be distinct and range from ‘1’ to ‘9’.Problem
Approach
Steps
Complexity
Input: The input consists of a string `pattern` of length `n`, where each character is either 'I' or 'D'.
Example: pattern = 'IIDID'
Constraints:
• 1 <= pattern.length <= 8
• pattern consists only of 'I' and 'D'.
Output: Return the lexicographically smallest string `num` that satisfies the pattern.
Example: Output: '123549876'
Constraints:
Goal: The goal is to construct the smallest lexicographical string `num` by following the constraints defined by the pattern.
Steps:
• 1. Traverse through the pattern and push the smallest available digits to a stack whenever encountering 'I'.
• 2. When encountering 'D', push digits into the stack and reverse them once 'I' is encountered or the end of the string is reached.
• 3. Append the digits from the stack to form the final number.
Goal: The string `pattern` contains only 'I' and 'D' characters and can be at most 8 characters long.
Steps:
• The pattern will always contain at least 1 character.
• The number of digits in `num` will be one greater than the length of the pattern.
Assumptions:
• The string `pattern` will always be valid, containing only 'I' and 'D'.
• The length of the string `num` will be equal to the length of the pattern plus one.
• Input: Input: pattern = 'IIDID'
• Explanation: In this case, we need to create a string such that at positions with 'I', the next number is greater, and at positions with 'D', the next number is smaller. The smallest valid string satisfying the pattern is '123549876'.
• Input: Input: pattern = 'DIDI'
• Explanation: Here, the smallest number satisfying the conditions is '4321'.
Approach: We can approach this problem by iterating through the `pattern` and using a stack to temporarily store numbers when encountering 'D'. When we encounter 'I', we pop from the stack to ensure the lexicographically smallest result.
Observations:
• We need to find a way to handle 'I' and 'D' constraints while maintaining the smallest lexicographical order.
• A stack will help us manage the numbers and reverse them when encountering a 'D'.
Steps:
• 1. Initialize a stack to keep track of the digits being processed.
• 2. Loop through the `pattern` string. For each 'I', push the next smallest digit to the stack.
• 3. When encountering 'D' or the end of the string, reverse the stack and append the digits to the result.
• 4. Return the resulting string after processing all characters.
Empty Inputs:
• The pattern will always have at least one character.
Large Inputs:
• The pattern length can go up to 8, and the solution must handle this efficiently.
Special Values:
• If the pattern consists entirely of 'I's or 'D's, handle the sequence accordingly.
Constraints:
• Ensure that the digits used in `num` are between '1' and '9' and are distinct.
string smallestNumber(string ptn) {
string res, stk;
int n = ptn.size();
for(int i = 0; i <= n; i++) {
stk.push_back(i + '1');
if(i == n || ptn[i] == 'I') {
while(!stk.empty()) {
res.push_back(stk.back());
stk.pop_back();
}
}
}
return res;
}
1 : Function Definition
string smallestNumber(string ptn) {
Defines the function `smallestNumber` that accepts a string `ptn` representing a pattern of 'I' (increasing) and 'D' (decreasing) and returns a string representing the smallest number that can be formed based on the pattern.
2 : Variable Initialization
string res, stk;
Initializes two strings: `res` to store the result and `stk` to act as a stack to manage the number sequence.
3 : Size Calculation
int n = ptn.size();
Calculates the length of the input pattern `ptn` and stores it in variable `n`.
4 : Loop Start
for(int i = 0; i <= n; i++) {
Starts a loop that iterates from `i = 0` to `i = n` to process each character in the pattern and the final number.
5 : Push to Stack
stk.push_back(i + '1');
Pushes the next number (i + 1) as a character (i.e., '1', '2', etc.) onto the stack `stk`.
6 : Check Pattern
if(i == n || ptn[i] == 'I') {
Checks if the end of the string has been reached (`i == n`) or if the current character in the pattern is 'I' (indicating an increasing sequence).
7 : Pop from Stack
while(!stk.empty()) {
Starts a while loop that runs as long as the stack is not empty, to pop elements from the stack in reverse order when a 'I' (increase) is encountered or when the end of the pattern is reached.
8 : Store in Result
res.push_back(stk.back());
Pops the top element from the stack and appends it to the result string `res`.
9 : Remove from Stack
stk.pop_back();
Removes the top element from the stack after adding it to the result.
10 : Return Statement
return res;
Returns the resulting string `res`, which contains the smallest number formed according to the given pattern.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) as we iterate through the string once and perform constant time operations for each character.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the stack used to hold intermediate values.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus