We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Construct Smallest Number From DI String

Number: 2456

Difficulty: Medium

Paid? No

Companies: Goldman Sachs, Amazon, josh technology, Meta

Problem Description

Given a pattern string consisting of characters 'I' (increasing) and 'D' (decreasing), construct the lexicographically smallest string of digits (from '1' to '9' with each digit used at most once) such that for every index i the following holds:

  • If pattern[i] == 'I', then num[i] < num[i+1].
  • If pattern[i] == 'D', then num[i] > num[i+1]. The constructed number should be of length pattern.length + 1.

Key Insights

  • The problem requires building a number that satisfies the relative order dictated by the pattern.
  • A greedy approach can be used by always choosing the smallest available digit.
  • Using a stack can efficiently reverse the order over segments where the pattern indicates decreasing order ('D').
  • By pushing digits onto the stack and then flushing it when an increasing order ('I') is encountered or at the end, the smallest lexicographical order is maintained.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the pattern (since each digit is processed once). Space Complexity: O(n), needed for the stack and the output storage.

Solution

The solution involves using a stack to temporarily hold digits in segments that need to be in reverse order. Iterate through the indices from 0 to n (n = pattern length) and do the following:

  1. Push the current digit (i+1) onto the stack.
  2. If the current character in the pattern is 'I' or if it is the last digit, then pop all digits from the stack and append them to the result. This reversal of the digits collected in the stack ensures that segments corresponding to a sequence of 'D's are reversed into the correct decreasing order.
  3. Continue this process until all digits are processed. The result will be the lexicographically smallest string that satisfies the given conditions.

The algorithm naturally handles both increasing and decreasing segments while ensuring no digit is repeated and the order is minimal.

Code Solutions

# Python solution using a stack approach

def smallestNumber(pattern):
    # Initialize an empty result list and a stack to hold digits temporarily
    result = []
    stack = []
    
    # Iterate through indices from 0 to len(pattern) inclusive
    for i in range(len(pattern) + 1):
        # Append the current digit (i+1) to the stack
        stack.append(str(i + 1))
        
        # If we reached the end or the current pattern character is 'I',
        # then flush all the digits from the stack to the result
        if i == len(pattern) or pattern[i] == 'I':
            while stack:
                result.append(stack.pop())
    
    # Join the result list into a final string
    return ''.join(result)

# Example usage:
print(smallestNumber("IIIDIDDD"))  # Expected Output: "123549876"
← Back to All Questions