Jobs

Interviews

Discussions

DI String Match

Easy

Asked by:

40 views

Topics:

ArraysGreedy Algorithms

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], and
s[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 <= 10⁵
s[i] is either 'I' or 'D'.

Try coding it in LeetCode

DI String Match

Easy

Asked by:

40 views

Topics:

ArraysGreedy Algorithms

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], and
s[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 <= 10⁵
s[i] is either 'I' or 'D'.

Try coding it in LeetCode

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 expected length of the input string `s`? Can I assume the string contains only 'I' and 'D' characters?
Is it possible for the input string `s` to be null or empty?
If there are multiple valid permutations of `0` to `n`, where `n` is the length of `s`, is any valid permutation acceptable as the output?
Should the integers in the output array be distinct, and guaranteed to be in the range [0, n] where n is the length of the input string?
Can you provide a specific example, perhaps with a shorter string like "ID", to illustrate the desired output?

Brute Force Solution

Approach

The core idea is to try out every single possible arrangement of numbers and see if any of them match the given pattern. We'll generate all possible number sequences and then check each one against the instructions to see if it's a valid solution.

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

First, imagine we have a set of numbers to pick from, starting at zero and going up to the length of the instruction string.
Start by guessing the first number in our sequence.
Then, guess the second number, making sure you don't repeat any numbers you've already used.
Continue guessing the next number until you have a full sequence of numbers.
Now, check if this sequence follows the instructions: if the instruction is 'I', the number must be increasing, and if it is 'D', the number must be decreasing.
If the sequence does not follow all the instructions, discard it and try a different arrangement.
Repeat this process until you find a sequence that perfectly matches the instructions.
If such a sequence is found, you've got your answer!

Code Implementation

def di_string_match_brute_force(instruction_string):
    string_length = len(instruction_string)
    possible_numbers = list(range(string_length + 1))
    permutations = find_all_permutations(possible_numbers)

    for permutation in permutations:
        if is_valid_permutation(permutation, instruction_string):
            return permutation

    return None

def find_all_permutations(numbers):
    if not numbers:
        return [[]]

    all_permutations = []
    for i in range(len(numbers)):
        first_number = numbers[i]
        remaining_numbers = numbers[:i] + numbers[i+1:]
        sub_permutations = find_all_permutations(remaining_numbers)
        for sub_permutation in sub_permutations:
            all_permutations.append([first_number] + sub_permutation)
    return all_permutations

def is_valid_permutation(permutation, instruction_string):
    # Check if the permutation matches the instruction string
    for i in range(len(instruction_string)):
        if instruction_string[i] == 'I':
            if permutation[i] > permutation[i+1]:
                return False
        elif instruction_string[i] == 'D':
            if permutation[i] < permutation[i+1]:
                return False

    return True

def di_string_match_brute_force_wrapper(instruction_string):
    result = di_string_match_brute_force(instruction_string)
    return result

Big(O) Analysis

Time Complexity

O(n!) – The algorithm generates all permutations of numbers from 0 to n, where n is the length of the input string S. Generating all permutations of n elements takes O(n!) time. For each permutation, the algorithm checks if it matches the DI string, which takes O(n) time. Therefore, the overall time complexity is dominated by the permutation generation, resulting in O(n! * n), which simplifies to O(n!). While the verification step inside the permutation generator could be thought of as O(n) it is dominated by the factorial generation of the sequence.

Space Complexity

O(N!) – The algorithm generates all possible permutations of numbers from 0 to N, where N is the length of the input string. Generating each permutation requires storing a sequence of length N. The number of such permutations is N!, meaning that potentially we need to store all N! permutations in memory. Furthermore, each recursive call adds a new frame to the call stack, potentially reaching a depth of N in the worst case. Therefore, the dominant factor affecting space is the generation of permutations, leading to O(N!) space complexity.

Optimal Solution

Approach

The challenge is to arrange numbers based on a sequence of instructions, either increasing ('I') or decreasing ('D'). The smart approach is to keep track of the smallest and largest available numbers and assign them based on the instruction at hand, working through the instructions one by one.

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

Start with the smallest possible number and the largest possible number available to you.
Look at the first instruction: If it's 'I' (increase), use the smallest available number and increase the smallest possible number.
If the first instruction is 'D' (decrease), use the largest available number and decrease the largest possible number.
Repeat this process for each instruction, always choosing the correct number based on the instruction and updating your range of available numbers.
After following all instructions, whatever number remains becomes the final number in the arrangement.

Code Implementation

def di_string_match(instructions):
    smallest_number = 0
    largest_number = len(instructions)
    result = []

    for instruction in instructions:
        # 'I' means we need to pick the smallest remaining number
        if instruction == 'I':
            result.append(smallest_number)
            smallest_number += 1

        # 'D' means we need to pick the largest remaining number
        else:
            result.append(largest_number)
            largest_number -= 1

    # Append the last remaining number.
    result.append(smallest_number)
    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string S of length n exactly once. In each iteration, it performs a constant-time operation: either appending the current smallest or largest available number to the result. Therefore, the time complexity is directly proportional to the length of the input string, resulting in a linear time complexity.

Space Complexity

O(N) – The algorithm uses an array of size N+1 to store the result, where N is the length of the input string S. This array is separate from the input and constitutes auxiliary space. The min and max variables only use constant space and do not depend on the input size. Therefore, the auxiliary space complexity is determined by the result array.

Edge Cases

Case	How to Handle
Null or empty input string S	Return an empty array if the input string is null or empty as no valid permutation can be generated.
Input string S with length 1	If the string length is 1, return [0, 1] for 'I' and [1, 0] for 'D'.
Input string S consisting only of 'I' characters	The algorithm should correctly produce an ascending sequence from 0 to N.
Input string S consisting only of 'D' characters	The algorithm should correctly produce a descending sequence from N to 0.
Input string S with alternating 'I' and 'D' characters (e.g., 'IDID')	The solution should correctly handle interleaving increasing and decreasing segments, producing the appropriate permutation.
Input string S close to maximum length as defined by problem constraints.	Ensure the solution uses memory efficiently and avoids potential stack overflow issues with iterative approach rather than recursion.
Invalid characters in the string S (other than 'I' or 'D')	Handle this case by either throwing an exception or ignoring the invalid characters and proceeding with the valid 'I' and 'D' characters present.
Integer overflow during calculation of high/low values.	This case is unlikely given the problem constraints on the size of the input string, but it can be addressed by checking intermediate calculations for overflow before assignments.

Null or empty input string S

How to Handle:

Return an empty array if the input string is null or empty as no valid permutation can be generated.

Input string S with length 1

How to Handle:

If the string length is 1, return [0, 1] for 'I' and [1, 0] for 'D'.

Input string S consisting only of 'I' characters

How to Handle:

The algorithm should correctly produce an ascending sequence from 0 to N.

Input string S consisting only of 'D' characters

How to Handle:

The algorithm should correctly produce a descending sequence from N to 0.

Input string S with alternating 'I' and 'D' characters (e.g., 'IDID')

How to Handle:

The solution should correctly handle interleaving increasing and decreasing segments, producing the appropriate permutation.

Input string S close to maximum length as defined by problem constraints.

How to Handle:

Ensure the solution uses memory efficiently and avoids potential stack overflow issues with iterative approach rather than recursion.

Invalid characters in the string S (other than 'I' or 'D')

How to Handle:

Handle this case by either throwing an exception or ignoring the invalid characters and proceeding with the valid 'I' and 'D' characters present.

Integer overflow during calculation of high/low values.

How to Handle:

This case is unlikely given the problem constraints on the size of the input string, but it can be addressed by checking intermediate calculations for overflow before assignments.

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 expected length of the input string `s`? Can I assume the string contains only 'I' and 'D' characters?
Is it possible for the input string `s` to be null or empty?
If there are multiple valid permutations of `0` to `n`, where `n` is the length of `s`, is any valid permutation acceptable as the output?
Should the integers in the output array be distinct, and guaranteed to be in the range [0, n] where n is the length of the input string?
Can you provide a specific example, perhaps with a shorter string like "ID", to illustrate the desired output?

Brute Force Solution

Approach

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

First, imagine we have a set of numbers to pick from, starting at zero and going up to the length of the instruction string.
Start by guessing the first number in our sequence.
Then, guess the second number, making sure you don't repeat any numbers you've already used.
Continue guessing the next number until you have a full sequence of numbers.
Now, check if this sequence follows the instructions: if the instruction is 'I', the number must be increasing, and if it is 'D', the number must be decreasing.
If the sequence does not follow all the instructions, discard it and try a different arrangement.
Repeat this process until you find a sequence that perfectly matches the instructions.
If such a sequence is found, you've got your answer!

Code Implementation

def di_string_match_brute_force(instruction_string):
    string_length = len(instruction_string)
    possible_numbers = list(range(string_length + 1))
    permutations = find_all_permutations(possible_numbers)

    for permutation in permutations:
        if is_valid_permutation(permutation, instruction_string):
            return permutation

    return None

def find_all_permutations(numbers):
    if not numbers:
        return [[]]

    all_permutations = []
    for i in range(len(numbers)):
        first_number = numbers[i]
        remaining_numbers = numbers[:i] + numbers[i+1:]
        sub_permutations = find_all_permutations(remaining_numbers)
        for sub_permutation in sub_permutations:
            all_permutations.append([first_number] + sub_permutation)
    return all_permutations

def is_valid_permutation(permutation, instruction_string):
    # Check if the permutation matches the instruction string
    for i in range(len(instruction_string)):
        if instruction_string[i] == 'I':
            if permutation[i] > permutation[i+1]:
                return False
        elif instruction_string[i] == 'D':
            if permutation[i] < permutation[i+1]:
                return False

    return True

def di_string_match_brute_force_wrapper(instruction_string):
    result = di_string_match_brute_force(instruction_string)
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with the smallest possible number and the largest possible number available to you.
Look at the first instruction: If it's 'I' (increase), use the smallest available number and increase the smallest possible number.
If the first instruction is 'D' (decrease), use the largest available number and decrease the largest possible number.
Repeat this process for each instruction, always choosing the correct number based on the instruction and updating your range of available numbers.
After following all instructions, whatever number remains becomes the final number in the arrangement.

Code Implementation

def di_string_match(instructions):
    smallest_number = 0
    largest_number = len(instructions)
    result = []

    for instruction in instructions:
        # 'I' means we need to pick the smallest remaining number
        if instruction == 'I':
            result.append(smallest_number)
            smallest_number += 1

        # 'D' means we need to pick the largest remaining number
        else:
            result.append(largest_number)
            largest_number -= 1

    # Append the last remaining number.
    result.append(smallest_number)
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string S	Return an empty array if the input string is null or empty as no valid permutation can be generated.
Input string S with length 1	If the string length is 1, return [0, 1] for 'I' and [1, 0] for 'D'.
Input string S consisting only of 'I' characters	The algorithm should correctly produce an ascending sequence from 0 to N.
Input string S consisting only of 'D' characters	The algorithm should correctly produce a descending sequence from N to 0.
Input string S with alternating 'I' and 'D' characters (e.g., 'IDID')	The solution should correctly handle interleaving increasing and decreasing segments, producing the appropriate permutation.
Input string S close to maximum length as defined by problem constraints.	Ensure the solution uses memory efficiently and avoids potential stack overflow issues with iterative approach rather than recursion.
Invalid characters in the string S (other than 'I' or 'D')	Handle this case by either throwing an exception or ignoring the invalid characters and proceeding with the valid 'I' and 'D' characters present.
Integer overflow during calculation of high/low values.	This case is unlikely given the problem constraints on the size of the input string, but it can be addressed by checking intermediate calculations for overflow before assignments.

Null or empty input string S

How to Handle:

Return an empty array if the input string is null or empty as no valid permutation can be generated.

Input string S with length 1

How to Handle:

If the string length is 1, return [0, 1] for 'I' and [1, 0] for 'D'.

Input string S consisting only of 'I' characters

How to Handle:

The algorithm should correctly produce an ascending sequence from 0 to N.

Input string S consisting only of 'D' characters

How to Handle:

The algorithm should correctly produce a descending sequence from N to 0.

Input string S with alternating 'I' and 'D' characters (e.g., 'IDID')

How to Handle:

The solution should correctly handle interleaving increasing and decreasing segments, producing the appropriate permutation.

Input string S close to maximum length as defined by problem constraints.

How to Handle:

Ensure the solution uses memory efficiently and avoids potential stack overflow issues with iterative approach rather than recursion.

Invalid characters in the string S (other than 'I' or 'D')

How to Handle:

Handle this case by either throwing an exception or ignoring the invalid characters and proceeding with the valid 'I' and 'D' characters present.

Integer overflow during calculation of high/low values.

How to Handle:

This case is unlikely given the problem constraints on the size of the input string, but it can be addressed by checking intermediate calculations for overflow before assignments.