Problem Description

You are given a string s that describes the relationship between consecutive elements in a permutation. The permutation contains all integers from 0 to n (where n is the length of string s), arranged in some order.

The string s works like this:

• If s[i] = 'I', it means the element at position i in the permutation is less than the element at position i+1 (increasing)
• If s[i] = 'D', it means the element at position i in the permutation is greater than the element at position i+1 (decreasing)

Your task is to construct any valid permutation that satisfies these conditions.

For example, if s = "IDID":

• The permutation has 5 elements (integers 0 through 4)
• s[0] = 'I' means perm[0] < perm[1]
• s[1] = 'D' means perm[1] > perm[2]
• s[2] = 'I' means perm[2] < perm[3]
• s[3] = 'D' means perm[3] > perm[4]

One valid permutation would be [0, 4, 1, 3, 2] because:

• 0 < 4 (satisfies 'I')
• 4 > 1 (satisfies 'D')
• 1 < 3 (satisfies 'I')
• 3 > 2 (satisfies 'D')

The solution uses a greedy approach with two pointers. It maintains low starting at 0 and high starting at n. When encountering 'I', it uses the current smallest available number (low), and when encountering 'D', it uses the current largest available number (high). This ensures all conditions are satisfied while using each number exactly once.

Intuition

Think about what happens when we see an 'I' - we need the current number to be smaller than the next one. The safest way to guarantee this is to use the smallest available number right now. Why? Because any number we place next will definitely be larger than the smallest possible value.

Similarly, when we see a 'D', we need the current number to be larger than the next one. The safest choice is to use the largest available number, because whatever comes next will definitely be smaller.

This greedy strategy works because:

1. When we place the smallest number for 'I', we're leaving room above it for future placements
2. When we place the largest number for 'D', we're leaving room below it for future placements

Let's trace through an example with s = "IDID":

• Start with available numbers [0, 1, 2, 3, 4]
• See 'I': Use smallest (0), now we have [1, 2, 3, 4] left
• See 'D': Use largest (4), now we have [1, 2, 3] left
• See 'I': Use smallest (1), now we have [2, 3] left
• See 'D': Use largest (3), now we have [2] left
• End of string: Use the last remaining number (2)

Result: [0, 4, 1, 3, 2]

The key insight is that by always choosing extremes (smallest for 'I', largest for 'D'), we create maximum "buffer space" between consecutive elements, ensuring the required relationships are always satisfied. This approach guarantees we'll never get stuck in a situation where we can't satisfy a future constraint.

Learn more about Greedy and Two Pointers patterns.

Solution Approach

The implementation uses a two-pointer greedy algorithm with the following steps:

1. Initialize two pointers:

   • low = 0 (tracks the smallest available number)
   • high = len(s) (tracks the largest available number, which equals n)

2. Create an empty result array ans to build our permutation.

3. Iterate through each character in string s:

   • If character is 'I':
     • Append low to the result array
     • Increment low by 1 (the next smallest available number)
   • If character is 'D':
     • Append high to the result array
     • Decrement high by 1 (the next largest available number)

4. Handle the last element: After processing all characters in s, we've placed n elements but need n+1 total. The last remaining number is low (which equals high at this point), so append it to complete the permutation.

Here's how the algorithm works step by step:

def diStringMatch(self, s: str) -> List[int]:
    low, high = 0, len(s)  # Initialize pointers
    ans = []
  
    for c in s:
        if c == "I":
            ans.append(low)  # Use smallest available
            low += 1         # Update smallest
        else:  # c == "D"
            ans.append(high) # Use largest available
            high -= 1        # Update largest
  
    ans.append(low)  # Add the last remaining number
    return ans

Time Complexity: O(n) where n is the length of string s. We traverse the string once.

Space Complexity: O(1) if we don't count the output array. We only use two integer variables for tracking.

The algorithm guarantees correctness because:

• When we place low for 'I', all remaining numbers are greater than low, ensuring the next number will be larger
• When we place high for 'D', all remaining numbers are smaller than high, ensuring the next number will be smaller
• We use each number from 0 to n exactly once

Example Walkthrough

Let's walk through the solution with s = "DI":

Step 1: Initialize

• String s = "DI" has length 2, so we need a permutation of [0, 1, 2]
• Set low = 0 (smallest available)
• Set high = 2 (largest available)
• Create empty result array ans = []

Step 2: Process first character 'D'

• Since it's 'D', we need current element > next element
• Use the largest available: append high = 2 to ans
• Update high = 2 - 1 = 1
• State: ans = [2], available numbers: [0, 1]

Step 3: Process second character 'I'

• Since it's 'I', we need current element < next element
• Use the smallest available: append low = 0 to ans
• Update low = 0 + 1 = 1
• State: ans = [2, 0], available numbers: [1]

Step 4: Add the last element

• We've processed all characters but need one more element
• Both low and high equal 1 (the only remaining number)
• Append low = 1 to ans
• Final result: ans = [2, 0, 1]

Verification:

• Position 0 to 1: 2 > 0 ✓ (satisfies 'D')
• Position 1 to 2: 0 < 1 ✓ (satisfies 'I')
• All numbers from 0 to 2 used exactly once ✓

The greedy strategy ensures we always have valid numbers available by using extremes - the largest for 'D' leaves smaller numbers for future use, and the smallest for 'I' leaves larger numbers for future use.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s.

The algorithm iterates through each character in the string s exactly once using a single for loop. Each iteration performs constant-time operations: comparing a character, appending to a list, and incrementing or decrementing a counter. After the loop, there's one additional append operation. Therefore, the total time complexity is O(n).

Space Complexity: O(n), where n is the length of the string s.

The algorithm creates an output list ans that stores n + 1 integers (one for each character in s plus one final append). The additional variables low and high use constant space O(1). Since the output array dominates the space usage with O(n + 1) = O(n) elements, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Add the Last Element

The most common mistake is forgetting that the permutation needs n+1 elements when the string has length n. After processing all characters in s, you've only placed n elements.

Incorrect Implementation:

def diStringMatch(self, s: str) -> List[int]:
    low, high = 0, len(s)
    ans = []
  
    for c in s:
        if c == "I":
            ans.append(low)
            low += 1
        else:
            ans.append(high)
            high -= 1
  
    # Missing: ans.append(low)
    return ans  # Returns only n elements instead of n+1

Solution: Always remember to append the final remaining number after the loop. At this point, low and high have converged to the same value, so you can append either one.

2. Incorrect Initial Values for Pointers

Another pitfall is initializing the pointers incorrectly, such as starting both at 0 or using wrong boundary values.

Incorrect Implementation:

def diStringMatch(self, s: str) -> List[int]:
    low, high = 0, len(s) - 1  # Wrong! high should be len(s)
    # or
    low, high = 1, len(s)  # Wrong! low should start at 0

Solution: Always initialize low = 0 (smallest value in range) and high = len(s) (largest value in range, which is n).

3. Off-by-One Error in Understanding the Problem

Some might misunderstand that the permutation should contain numbers from 1 to n or from 0 to n-1.

Incorrect Understanding:

# Wrong: Using 1 to n instead of 0 to n
low, high = 1, len(s) + 1

Solution: Carefully read the problem - the permutation contains all integers from 0 to n inclusive, where n = len(s).

4. Using the Wrong Pointer for Each Character

Mixing up when to use low vs high will produce an incorrect permutation.

Incorrect Implementation:

for c in s:
    if c == "I":
        ans.append(high)  # Wrong! Should use low for 'I'
        high -= 1
    else:
        ans.append(low)   # Wrong! Should use high for 'D'
        low += 1

Solution: Remember the mnemonic:

• 'I' for Increase → use the smallest (low) to guarantee the next can be larger
• 'D' for Decrease → use the largest (high) to guarantee the next can be smaller