2375. Construct Smallest Number From DI String - Detailed Explanation

Problem Statement

Given a string s consisting only of the characters 'I' (for "increasing") and 'D' (for "decreasing"), construct the lexicographically smallest permutation of the numbers 1 to n+1 (where n is the length of s) that satisfies the following conditions:

• For every index i (0-indexed) in s:
  • If s[i] == 'I', then result[i] < result[i+1].
  • If s[i] == 'D', then result[i] > result[i+1].

Return the resulting permutation as an array (or string representation, depending on the requirements).

Examples

Example 1

Input:

s = "IDID"

Output:

[1, 3, 2, 5, 4]

Explanation:

• The string length is 4, so we need to form a permutation of [1, 2, 3, 4, 5].
• The pattern is:
  • s[0] = 'I' implies result[0] < result[1]
  • s[1] = 'D' implies result[1] > result[2]
  • s[2] = 'I' implies result[2] < result[3]
  • s[3] = 'D' implies result[3] > result[4]
• One optimal (and smallest) permutation that satisfies these conditions is [1, 3, 2, 5, 4].

Example 2

Input:

s = "III"

Output:

[1, 2, 3, 4]

Explanation:

• For a string of three 'I' characters, the condition is strictly increasing.
• The lexicographically smallest permutation is simply the sorted order: [1, 2, 3, 4].

Example 3

Input:

s = "DDI"

Output:

[3, 2, 1, 4]

Explanation:

• For the first two positions, we have 'D', so we need a decreasing sequence.
• One optimal solution is to assign [3, 2, 1] for the first three positions (satisfying both D's) and then since s[2] is 'I', result[2] < result[3] so we append 4.
• Thus, [3, 2, 1, 4] is the lexicographically smallest permutation that meets the criteria.

Hints

1. Observation on Blocks:
   Notice that the pattern of consecutive 'D' characters indicates that you must reverse a block of numbers. For example, if you see "DDD", the corresponding numbers should appear in decreasing order. Conversely, when you see an 'I', you can assign the smallest available number.

2. Using a Stack:
   One common approach is to use a stack to simulate the reversal of blocks. Iterate from 0 to n (n = length of s) and:

   • Push the current number (i+1) onto the stack.
   • When you encounter an 'I' (or when you reach the end), pop all elements from the stack and append them to the result. This effectively reverses the numbers that were pushed for the consecutive 'D' characters.

3. Alternate Approach:
   Another approach is to start with the sorted list [1, 2, …, n+1] and for every consecutive block of 'D' characters, reverse that section of the list.

Approaches

Approach 1: Stack-Based Simulation

Idea:
Iterate through the numbers from 1 to n+1. For each number, push it onto a stack. When you see an 'I' in the input (or when you have processed all characters), pop all elements from the stack and append them to the result list. This reverses the order of numbers corresponding to a block of 'D' characters.

Steps:

1. Initialize an empty stack and an empty result list.
2. For i from 0 to n (where n = length of s):
   • Push (i+1) onto the stack.
   • If i equals n or s[i] == 'I':
     • While the stack is not empty, pop from the stack and add the popped number to the result.
3. Return the result.

Example Walkthrough ("IDID"):

• i = 0:
  • Push 1.
  • s[0] = 'I', so pop from stack → result becomes [1].
• i = 1:
  • Push 2.
  • s[1] = 'D', so do nothing.
• i = 2:
  • Push 3.
  • s[2] = 'I', so now pop stack: pop 3 then 2 → result becomes [1, 3, 2].
• i = 3:
  • Push 4.
  • s[3] = 'D', so do nothing.
• i = 4 (i == n):
  • Push 5.
  • Since i == n, pop stack: pop 5 then 4 → result becomes [1, 3, 2, 5, 4].

Approach 2: Direct Reversal of Blocks

Idea:
Start with an array of numbers from 1 to n+1. Iterate through the string s and for each continuous block of 'D', reverse that segment in the result array.

Code Implementation

Python Code