2375. Construct Smallest Number From DI String - Detailed Explanation

Problem Statement

You are given a string s consisting only of the characters 'D' and 'I'. Let n = s.length. You need to construct the lexicographically smallest permutation of the numbers 1 to n + 1 that satisfies the following conditions for every index i (0-indexed):

• If s[i] == 'I', then the (i)th number is less than the ((i+1))th number.
• If s[i] == 'D', then the (i)th number is greater than the ((i+1))th number.

Return the constructed number as a string.

Example 1

• Input: s = "I"
• Explanation:
  • ( n = 1 ) so we use numbers ([1, 2]).
  • The condition is that the first number must be less than the second.
  • The smallest such number is "12".
• Output: "12"

Example 2

• Input: s = "DI"
• Explanation:
  • ( n = 2 ) so we use numbers ([1, 2, 3]).
  • For index 0, 'D' requires: first number > second number.
  • For index 1, 'I' requires: second number < third number.
  • The lexicographically smallest number meeting these conditions is "213".
• Output: "213"

Example 3

• Input: s = "DDI"
• Explanation:
  • ( n = 3 ) so we use numbers ([1, 2, 3, 4]).
  • The pattern: first number > second (D), second > third (D), third < fourth (I).
  • The smallest valid sequence is "3214".
• Output: "3214"

Hints

1. Observing the Pattern:
   When you see a consecutive group of 'D' characters, the corresponding numbers must form a descending sequence. When you hit an 'I' (or reach the end of the string), it signals that you can “flush” or output the descending group in reverse order to get the smallest possible lexicographic order.

2. Using a Stack:
   A stack can help “store” the numbers while you process a group of 'D' characters. When you encounter an 'I' (or reach the end), you can pop all numbers from the stack (which will reverse the order) and add them to your result.

Approach 1: Stack-Based Greedy Construction

Explanation

1. Initialize a Stack and Result:
   Create an empty stack and an empty result list (or string).

2. Iterate Through the Indices:
   Loop from i = 0 to n (inclusive). For each iteration, push the number i+1 onto the stack.

   • Why ( i+1 )?
     Because we need to use numbers from 1 to n + 1.

3. Flushing the Stack:
   If you are at the end of the string (i.e. ( i == n )) or if the current character s[i] == 'I', it means the current descending sequence (if any) ends here. Pop all the numbers from the stack and add them to the result. Popping reverses the order, fulfilling the descending requirement for the 'D' pattern, and it produces the lexicographically smallest order when merged with previous parts.

4. Result:
   After processing all characters, the concatenated result is your answer.

Visual Walkthrough

For example, take s = "DI":

• Iteration 0:

  • Push 1 onto the stack.
  • s[0] is 'D', so do not flush.

• Iteration 1:

  • Push 2 onto the stack.
  • s[1] is 'I', so flush: pop from the stack yields 2, then 1.
  • Result becomes: "21"

• Iteration 2 (i = n):

  • Push 3 onto the stack.
  • We are at the end so flush: pop 3.
  • Append to result → Final result: "21" + "3" = "213"

Code Solutions

Python Code