Construct Smallest Number From DI String

Medium

Goldman Sachs

2 views

Topics:

StringsGreedy Algorithms

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.
If pattern[i] == 'I', then num[i] < num[i + 1].
If 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 <= 8
pattern consists of only the letters 'I' and 'D'.

Construct Smallest Number From DI String

Medium

Goldman Sachs

2 views

Topics:

StringsGreedy Algorithms

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.
If pattern[i] == 'I', then num[i] < num[i + 1].
If 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 <= 8
pattern consists of only the letters 'I' and 'D'.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `S`?
Can the input string `S` contain characters other than 'D' and 'I'?
If the input string `S` is empty, what should the output be?
If multiple smallest numbers can be constructed, is any one acceptable?
Are there any leading zeros allowed in the output number?

Brute Force Solution

Approach

The brute force approach involves trying every single possible number combination that fits the given length and checking if it follows the 'I' and 'D' instructions. We generate all possible number sequences and validate them one by one.

Here's how the algorithm would work step-by-step:

Start with the smallest possible number sequence of the required length, using digits from 1 to the length plus 1, without repeating any digit.
Check if this sequence satisfies all the 'I' and 'D' instructions in the input string. For instance, if the input says 'I', the number in the sequence must be increasing compared to the previous number. If it says 'D', the number must be decreasing.
If the sequence doesn't satisfy the instructions, generate the next possible sequence.
Repeat the checking and generating process for all possible number sequences.
Keep track of all the sequences that actually satisfy the given instructions.
From all the valid sequences we found, choose the very smallest one. This is our answer.

Code Implementation

def construct_smallest_number_brute_force(di_string):
    number_length = len(di_string) + 1
    smallest_number = None

    import itertools
    # Generate all possible permutations of numbers from 1 to number_length
    for permutation in itertools.permutations(range(1, number_length + 1)):
        number_string = "".join(map(str, permutation))
        is_valid = True

        # Check if the current number string satisfies the DI string pattern
        for index in range(len(di_string)):
            if di_string[index] == 'I' and permutation[index] >= permutation[index + 1]:
                is_valid = False
                break
            elif di_string[index] == 'D' and permutation[index] <= permutation[index + 1]:
                is_valid = False
                break

        # If the current number string is valid, update smallest_number if necessary
        if is_valid:
            #If smallest_number is None or current number is smaller
            if smallest_number is None or int(number_string) < int(smallest_number):
                smallest_number = number_string

    return smallest_number

Big(O) Analysis

Time Complexity

O((n+1)! * n) – The brute force approach iterates through all possible permutations of numbers from 1 to n+1, where n is the length of the input string. There are (n+1)! such permutations. For each permutation, we validate it against the input string of length n, which requires O(n) time. Therefore, the total time complexity is the product of the number of permutations and the time to validate each one, resulting in O((n+1)! * n).

Space Complexity

O(N!) – The brute force approach generates all possible number sequences of length N+1, where N is the length of the input string. Generating all permutations of N+1 numbers requires storing a temporary sequence, which can grow up to size N+1. In the worst case, we might need to store all possible permutations before finding the smallest valid one. Since there are (N+1)! permutations of N+1 numbers, the space complexity to store these permutations is O((N+1)!). This simplifies to O(N!).

Optimal Solution

Approach

The core idea is to build the smallest number digit by digit, using the 'D' and 'I' characters to guide our choices. We use the 'D' characters to build descending sequences and the 'I' characters to build ascending ones, always picking the smallest available digit.

Here's how the algorithm would work step-by-step:

Imagine you have a set of numbers you haven't used yet, starting with 1, 2, 3, and so on.
Begin with an empty number string.
Look at the first instruction ('D' or 'I').
If it's 'I', find the smallest unused number and put it in the string. You know you will need to increase from here.
If it's 'D', you need a descending sequence. Look ahead to see how many consecutive 'D's there are.
Then, find the largest number available that will be the start of the descending sequence. Fill in the rest of the descending sequence.
Mark all the used numbers.
Repeat until all instructions are processed.
If any numbers remain unused, add them to the end in increasing order.

Code Implementation

def construct_smallest_number_from_di_string(di_string):
    result = ""
    available_numbers = list(range(1, len(di_string) + 2))
    
    string_index = 0
    while string_index < len(di_string):
        if di_string[string_index] == 'I':
            #If 'I', use the smallest available number.
            smallest_number = min(available_numbers)
            result += str(smallest_number)
            available_numbers.remove(smallest_number)
            string_index += 1
        else:
            #If 'D', look ahead to see how many consecutive 'D's there are.
            descending_count = 0
            while string_index + descending_count < len(di_string) and \
                  di_string[string_index + descending_count] == 'D':
                descending_count += 1

            #Find the largest available number for the start of descending sequence.
            largest_number_for_descending = sorted(available_numbers)[-descending_count -1]

            #Build descending sequence
            for i in range(descending_count + 1):
                current_number = largest_number_for_descending + i - descending_count
                result += str(current_number)
                available_numbers.remove(current_number)
            string_index += descending_count

    # Append any remaining available numbers to the result.
    for number in sorted(available_numbers):
        result += str(number)

    return result

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input string of length n. In the case of 'D' characters, it looks ahead to find consecutive 'D's, potentially scanning a portion of the remaining input string in each iteration. The worst-case scenario involves several consecutive 'D' sequences, each requiring a scan proportional to the number of remaining characters. The construction of the descending sequence might require finding the largest unused number among the remaining numbers, contributing to O(n) within each iteration of the main loop. In the worst case these nested operations approximate to n * n/2, simplifying to O(n²).

Space Complexity

O(N) – The algorithm constructs a string representing the smallest number. The length of this string is directly proportional to the number of digits needed, which corresponds to the length of the input DI string plus one. Therefore, storing the result string requires O(N) space, where N is the length of the input string. Additionally, although not explicitly mentioned, keeping track of the used numbers conceptually needs space proportional to the length of result string. Hence, the auxiliary space is O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string or throw an IllegalArgumentException, depending on the specified behavior in the problem description.
Input string contains characters other than 'I' or 'D'	Throw an IllegalArgumentException as the input should only contain 'I' and 'D' characters.
Input string is very long (approaching system limits)	Ensure the algorithm uses a reasonable amount of memory and avoids stack overflow errors, possibly requiring an iterative rather than recursive approach.
Input string consists of all 'I' characters	The smallest number is simply an ascending sequence (1, 2, 3, ...), so the algorithm should produce this correctly.
Input string consists of all 'D' characters	The smallest number is a descending sequence (n, n-1, ..., 1), which needs to be handled correctly, particularly at the boundaries.
Input string starts or ends with 'I' or 'D'	The algorithm should correctly handle these boundary conditions to ensure the resulting number is the smallest possible.
Consecutive 'I's or 'D's in the input string	The algorithm should appropriately manage the sequence of increasing or decreasing numbers based on the consecutive 'I's and 'D's.
Length of the string exceeds the maximum representable integer	The solution should use strings to represent the result or handle cases where the number of digits could cause an overflow.