Form minimum number from given sequence

Auxiliary Given a pattern containing only I's and D's. I for increasing and D for decreasing. Device an algorithm to print the minimum number following that pattern. Digits from 1-9 and digits can’t repeat.

Examples: 

 Input: D Output: 21 Input: I Output: 12 Input: DD Output: 321 Input: II Output: 123 Input: DIDI Output: 21435 Input: IIDDD Output: 126543 Input: DDIDDIID Output: 321654798

Source: Amazon Interview Question

We strongly recommend that you click here and practice it, before moving on to the solution.

Below are some important observations

Since digits can't repeat, there can be at most 9 digits in output. 

Also, number of digits in output is one more than number of characters in input. Note that the first character of input corresponds to two digits in output.

Idea is to iterate over input array and keep track of last printed digit and maximum digit printed so far. 

Steps were to follow to solve this problem:

• Create a static function named "PrintMinNumberForPattern" that takes a string array arr as input.
• Create two variables "curr_max" and "last_entry" and initialize them to 0.
• Traverse through the input array arr using a for a loop.
• Create a variable "noOfNextD" and initialize it to 0.
• If the character at index i is 'I', perform the following steps:
  • Find the number of next consecutive D's available by iterating over the array from the next index until a non-'D'                                 character is encountered.
  •  If i is 0, set curr_max to noOfNextD+2 and print the incremented sequence from 1.
  • If i is not 0, set curr_max to curr_max + noOfNextD + 1 and print the digit for 'I'.
  •  For all next consecutive 'D' characters, print the decremented sequence.
• If the character at index i is 'D', perform the following steps:
  •  If i is 0, find the number of the next consecutive 'D' characters available and set curr_max to noOfNextD+2. Print the first                        two digits (curr_max and curr_max-1).
  •  If i is not 0, print the decremented value of last_entry.
• Print a newline character after the for loop completes.

Below is the implementation of the above idea:

// C++ program to print minimum number that can be formed // from a given sequence of Is and Ds #include <bits/stdc++.h> using namespace std; // Prints the minimum number that can be formed from // input sequence of I's and D's void PrintMinNumberForPattern(string arr) {  // Initialize current_max (to make sure that  // we don't use repeated character  int curr_max = 0;  // Initialize last_entry (Keeps track for  // last printed digit)  int last_entry = 0;  int j;  // Iterate over input array  for (int i=0; i<arr.length(); i++)  {  // Initialize 'noOfNextD' to get count of  // next D's available  int noOfNextD = 0;  switch(arr[i])  {  case 'I':  // If letter is 'I'  // Calculate number of next consecutive D's  // available  j = i+1;  while (arr[j] == 'D' && j < arr.length())  {  noOfNextD++;  j++;  }    if (i==0)  {  curr_max = noOfNextD + 2;  // If 'I' is first letter, print incremented  // sequence from 1  cout << " " << ++last_entry;  cout << " " << curr_max;  // Set max digit reached  last_entry = curr_max;  }  else  {  // If not first letter  // Get next digit to print  curr_max = curr_max + noOfNextD + 1;  // Print digit for I  last_entry = curr_max;  cout << " " << last_entry;  }  // For all next consecutive 'D' print   // decremented sequence  for (int k=0; k<noOfNextD; k++)  {  cout << " " << --last_entry;  i++;  }  break;  // If letter is 'D'  case 'D':  if (i == 0)  {  // If 'D' is first letter in sequence  // Find number of Next D's available  j = i+1;  while (arr[j] == 'D' && j < arr.length())  {  noOfNextD++;  j++;  }  // Calculate first digit to print based on   // number of consecutive D's  curr_max = noOfNextD + 2;  // Print twice for the first time  cout << " " << curr_max << " " << curr_max - 1;  // Store last entry  last_entry = curr_max - 1;  }  else  {  // If current 'D' is not first letter  // Decrement last_entry  cout << " " << last_entry - 1;  last_entry--;  }  break;  }  }  cout << endl; } // Driver program to test above int main() {  PrintMinNumberForPattern("IDID");  PrintMinNumberForPattern("I");  PrintMinNumberForPattern("DD");  PrintMinNumberForPattern("II");  PrintMinNumberForPattern("DIDI");  PrintMinNumberForPattern("IIDDD");  PrintMinNumberForPattern("DDIDDIID");  return 0; } 

// Java program to print minimum number that can be formed  // from a given sequence of Is and Ds  class GFG  {    // Prints the minimum number that can be formed from   // input sequence of I's and D's   static void PrintMinNumberForPattern(String arr)   {  // Initialize current_max (to make sure that   // we don't use repeated character   int curr_max = 0;  // Initialize last_entry (Keeps track for   // last printed digit)   int last_entry = 0;  int j;  // Iterate over input array   for (int i = 0; i < arr.length(); i++)   {  // Initialize 'noOfNextD' to get count of   // next D's available   int noOfNextD = 0;  switch (arr.charAt(i))  {  case 'I':  // If letter is 'I'   // Calculate number of next consecutive D's   // available   j = i + 1;  while (j < arr.length() && arr.charAt(j) == 'D')   {  noOfNextD++;  j++;  }  if (i == 0)   {  curr_max = noOfNextD + 2;  // If 'I' is first letter, print incremented   // sequence from 1   System.out.print(" " + ++last_entry);  System.out.print(" " + curr_max);  // Set max digit reached   last_entry = curr_max;  }   else   {  // If not first letter   // Get next digit to print   curr_max = curr_max + noOfNextD + 1;  // Print digit for I   last_entry = curr_max;  System.out.print(" " + last_entry);  }  // For all next consecutive 'D' print   // decremented sequence   for (int k = 0; k < noOfNextD; k++)  {  System.out.print(" " + --last_entry);  i++;  }  break;  // If letter is 'D'   case 'D':  if (i == 0)  {  // If 'D' is first letter in sequence   // Find number of Next D's available   j = i + 1;  while (j < arr.length()&&arr.charAt(j) == 'D')   {  noOfNextD++;  j++;  }  // Calculate first digit to print based on   // number of consecutive D's   curr_max = noOfNextD + 2;  // Print twice for the first time   System.out.print(" " + curr_max + " " + (curr_max - 1));  // Store last entry   last_entry = curr_max - 1;  }   else  {  // If current 'D' is not first letter   // Decrement last_entry   System.out.print(" " + (last_entry - 1));  last_entry--;  }  break;  }  }  System.out.println();  }  // Driver code   public static void main(String[] args)   {  PrintMinNumberForPattern("IDID");  PrintMinNumberForPattern("I");  PrintMinNumberForPattern("DD");  PrintMinNumberForPattern("II");  PrintMinNumberForPattern("DIDI");  PrintMinNumberForPattern("IIDDD");  PrintMinNumberForPattern("DDIDDIID");  } } // This code is contributed by Princi Singh 

# Python3 program to print minimum number that # can be formed from a given sequence of Is and Ds # Prints the minimum number that can be formed from # input sequence of I's and D's def PrintMinNumberForPattern(arr): # Initialize current_max (to make sure that # we don't use repeated character curr_max = 0 # Initialize last_entry (Keeps track for # last printed digit) last_entry = 0 i = 0 # Iterate over input array while i < len(arr): # Initialize 'noOfNextD' to get count of # next D's available noOfNextD = 0 if arr[i] == "I": # If letter is 'I' # Calculate number of next consecutive D's # available j = i + 1 while j < len(arr) and arr[j] == "D": noOfNextD += 1 j += 1 if i == 0: curr_max = noOfNextD + 2 last_entry += 1 # If 'I' is first letter, print incremented # sequence from 1 print("", last_entry, end = "") print("", curr_max, end = "") # Set max digit reached last_entry = curr_max else: # If not first letter # Get next digit to print curr_max += noOfNextD + 1 # Print digit for I last_entry = curr_max print("", last_entry, end = "") # For all next consecutive 'D' print # decremented sequence for k in range(noOfNextD): last_entry -= 1 print("", last_entry, end = "") i += 1 # If letter is 'D' elif arr[i] == "D": if i == 0: # If 'D' is first letter in sequence # Find number of Next D's available j = i + 1 while j < len(arr) and arr[j] == "D": noOfNextD += 1 j += 1 # Calculate first digit to print based on # number of consecutive D's curr_max = noOfNextD + 2 # Print twice for the first time print("", curr_max, curr_max - 1, end = "") # Store last entry last_entry = curr_max - 1 else: # If current 'D' is not first letter # Decrement last_entry print("", last_entry - 1, end = "") last_entry -= 1 i += 1 print() # Driver code if __name__ == "__main__": PrintMinNumberForPattern("IDID") PrintMinNumberForPattern("I") PrintMinNumberForPattern("DD") PrintMinNumberForPattern("II") PrintMinNumberForPattern("DIDI") PrintMinNumberForPattern("IIDDD") PrintMinNumberForPattern("DDIDDIID") # This code is contributed by # sanjeev2552 

// C# program to print minimum number that can be formed  // from a given sequence of Is and Ds  using System;   class GFG  {    // Prints the minimum number that can be formed from   // input sequence of I's and D's   static void PrintMinNumberForPattern(String arr)   {  // Initialize current_max (to make sure that   // we don't use repeated character   int curr_max = 0;  // Initialize last_entry (Keeps track for   // last printed digit)   int last_entry = 0;  int j;  // Iterate over input array   for (int i = 0; i < arr.Length; i++)   {  // Initialize 'noOfNextD' to get count of   // next D's available   int noOfNextD = 0;  switch (arr[i])  {  case 'I':  // If letter is 'I'   // Calculate number of next consecutive D's   // available   j = i + 1;  while (j < arr.Length && arr[j] == 'D')   {  noOfNextD++;  j++;  }  if (i == 0)   {  curr_max = noOfNextD + 2;  // If 'I' is first letter, print incremented   // sequence from 1   Console.Write(" " + ++last_entry);  Console.Write(" " + curr_max);  // Set max digit reached   last_entry = curr_max;  }   else  {  // If not first letter   // Get next digit to print   curr_max = curr_max + noOfNextD + 1;  // Print digit for I   last_entry = curr_max;  Console.Write(" " + last_entry);  }  // For all next consecutive 'D' print   // decremented sequence   for (int k = 0; k < noOfNextD; k++)  {  Console.Write(" " + --last_entry);  i++;  }  break;  // If letter is 'D'   case 'D':  if (i == 0)  {  // If 'D' is first letter in sequence   // Find number of Next D's available   j = i + 1;  while (j < arr.Length&&arr[j] == 'D')   {  noOfNextD++;  j++;  }  // Calculate first digit to print based on   // number of consecutive D's   curr_max = noOfNextD + 2;  // Print twice for the first time   Console.Write(" " + curr_max + " " + (curr_max - 1));  // Store last entry   last_entry = curr_max - 1;  }   else  {  // If current 'D' is not first letter   // Decrement last_entry   Console.Write(" " + (last_entry - 1));  last_entry--;  }  break;  }  }  Console.WriteLine();  }  // Driver code   public static void Main(String[] args)   {  PrintMinNumberForPattern("IDID");  PrintMinNumberForPattern("I");  PrintMinNumberForPattern("DD");  PrintMinNumberForPattern("II");  PrintMinNumberForPattern("DIDI");  PrintMinNumberForPattern("IIDDD");  PrintMinNumberForPattern("DDIDDIID");  } } // This code is contributed by Princi Singh 

<?php // PHP program to print minimum // number that can be formed // from a given sequence of  // Is and Ds // Prints the minimum number  // that can be formed from // input sequence of I's and D's function PrintMinNumberForPattern($arr) { // Initialize current_max  // (to make sure that // we don't use repeated  // character $curr_max = 0; // Initialize last_entry  // (Keeps track for // last printed digit) $last_entry = 0; $j; // Iterate over // input array for ($i = 0; $i < strlen($arr); $i++) { // Initialize 'noOfNextD' // to get count of // next D's available $noOfNextD = 0; switch($arr[$i]) { case 'I': // If letter is 'I' // Calculate number of  // next consecutive D's // available $j = $i + 1; while ($arr[$j] == 'D' && $j < strlen($arr)) { $noOfNextD++; $j++; } if ($i == 0) { $curr_max = $noOfNextD + 2; // If 'I' is first letter,  // print incremented // sequence from 1 echo " " , ++$last_entry; echo " " , $curr_max; // Set max  // digit reached $last_entry = $curr_max; } else { // If not first letter // Get next digit // to print $curr_max = $curr_max + $noOfNextD + 1; // Print digit for I $last_entry = $curr_max; echo " " , $last_entry; } // For all next consecutive 'D'  // print decremented sequence for ($k = 0; $k < $noOfNextD; $k++) { echo " " , --$last_entry; $i++; } break; // If letter is 'D' case 'D': if ($i == 0) { // If 'D' is first letter  // in sequence. Find number // of Next D's available $j = $i+1; while (($arr[$j] == 'D') && ($j < strlen($arr))) { $noOfNextD++; $j++; } // Calculate first digit  // to print based on  // number of consecutive D's $curr_max = $noOfNextD + 2; // Print twice for // the first time echo " " , $curr_max , " " ,$curr_max - 1; // Store last entry $last_entry = $curr_max - 1; } else { // If current 'D'  // is not first letter // Decrement last_entry echo " " , $last_entry - 1; $last_entry--; } break; } } echo "\n"; } // Driver Code PrintMinNumberForPattern("IDID"); PrintMinNumberForPattern("I"); PrintMinNumberForPattern("DD"); PrintMinNumberForPattern("II"); PrintMinNumberForPattern("DIDI"); PrintMinNumberForPattern("IIDDD"); PrintMinNumberForPattern("DDIDDIID"); // This code is contributed by aj_36 ?> 

<script> // Javascript program to print minimum number that can be formed // from a given sequence of Is and Ds // Prints the minimum number that can be formed from  // input sequence of I's and D's function PrintMinNumberForPattern(arr) {  // Initialize current_max (to make sure that  // we don't use repeated character  let curr_max = 0;    // Initialize last_entry (Keeps track for  // last printed digit)  let last_entry = 0;    let j;    // Iterate over input array  for (let i = 0; i < arr.length; i++)  {  // Initialize 'noOfNextD' to get count of  // next D's available  let noOfNextD = 0;    switch (arr[i])  {  case 'I':  // If letter is 'I'    // Calculate number of next consecutive D's  // available  j = i + 1;  while (j < arr.length && arr[j] == 'D')  {  noOfNextD++;  j++;  }    if (i == 0)  {  curr_max = noOfNextD + 2;    // If 'I' is first letter, print incremented  // sequence from 1  document.write(" " + ++last_entry);  document.write(" " + curr_max);    // Set max digit reached  last_entry = curr_max;  }  else  {  // If not first letter    // Get next digit to print  curr_max = curr_max + noOfNextD + 1;    // Print digit for I  last_entry = curr_max;  document.write(" " + last_entry);  }    // For all next consecutive 'D' print  // decremented sequence  for (let k = 0; k < noOfNextD; k++)  {  document.write(" " + --last_entry);  i++;  }  break;    // If letter is 'D'  case 'D':  if (i == 0)  {  // If 'D' is first letter in sequence  // Find number of Next D's available  j = i + 1;  while (j < arr.length && arr[j] == 'D')  {  noOfNextD++;  j++;  }    // Calculate first digit to print based on  // number of consecutive D's  curr_max = noOfNextD + 2;    // Print twice for the first time  document.write(" " + curr_max + " " + (curr_max - 1));    // Store last entry  last_entry = curr_max - 1;  }  else  {  // If current 'D' is not first letter    // Decrement last_entry  document.write(" " + (last_entry - 1));  last_entry--;  }  break;  }  }  document.write("<br>"); } // Driver code PrintMinNumberForPattern("IDID"); PrintMinNumberForPattern("I"); PrintMinNumberForPattern("DD"); PrintMinNumberForPattern("II"); PrintMinNumberForPattern("DIDI"); PrintMinNumberForPattern("IIDDD"); PrintMinNumberForPattern("DDIDDIID"); // This code is contributed by ab2127 </script> 

 1 3 2 5 4 1 2 3 2 1 1 2 3 2 1 4 3 5 1 2 6 5 4 3 3 2 1 6 5 4 7 9 8

Time Complexity: O(N^2), overall time complexity. Where, N is the length of the string.
Auxiliary Space: O(1).

This solution is suggested by Swapnil Trambake.

Alternate Solution: 
Let's observe a few facts in case of a minimum number: 

• The digits can't repeat hence there can be 9 digits at most in output.
• To form a minimum number , at every index of the output, we are interested in the minimum number which can be placed at that index.

The idea is to iterate over the entire input array , keeping track of the minimum number (1-9) which can be placed at that position of the output.

The tricky part of course occurs when 'D' is encountered at index other than 0. In such a case we have to track the nearest 'I' to the left of 'D' and increment each number in the output vector by 1 in between 'I' and 'D'. 
We cover the base case as follows: 

• If the first character of input is 'I' then we append 1 and 2 in the output vector and the minimum available number is set to 3 .The index of most recent 'I' is set to 1.
• If the first character of input is 'D' then we append 2 and 1 in the output vector and the minimum available number is set to 3, and the index of most recent 'I' is set to 0.

Now we iterate the input string from index 1 till its end and: 

• If the character scanned is 'I' , a minimum value that has not been used yet is appended to the output vector .We increment the value of minimum no. available and index of most recent 'I' is also updated.
• If the character scanned is 'D' at index i of input array, we append the ith element from output vector in the output and track the nearest 'I' to the left of 'D' and increment each number in the output vector by 1 in between 'I' and 'D'.

Following is the program for the same: 

// C++ program to print minimum number that can be formed // from a given sequence of Is and Ds #include<bits/stdc++.h> using namespace std; void printLeast(string arr) {  // min_avail represents the minimum number which is  // still available for inserting in the output vector.  // pos_of_I keeps track of the most recent index  // where 'I' was encountered w.r.t the output vector  int min_avail = 1, pos_of_I = 0;  //vector to store the output  vector<int>v;  // cover the base cases  if (arr[0]=='I')  {  v.push_back(1);  v.push_back(2);  min_avail = 3;  pos_of_I = 1;  }  else  {  v.push_back(2);  v.push_back(1);  min_avail = 3;  pos_of_I = 0;  }  // Traverse rest of the input  for (int i=1; i<arr.length(); i++)  {  if (arr[i]=='I')  {  v.push_back(min_avail);  min_avail++;  pos_of_I = i+1;  }  else  {  v.push_back(v[i]);  for (int j=pos_of_I; j<=i; j++)  v[j]++;  min_avail++;  }  }  // print the number  for (int i=0; i<v.size(); i++)  cout << v[i] << " ";  cout << endl; } // Driver program to check the above function int main() {  printLeast("IDID");  printLeast("I");  printLeast("DD");  printLeast("II");  printLeast("DIDI");  printLeast("IIDDD");  printLeast("DDIDDIID");  return 0; } 

// Java program to print minimum number that can be formed  // from a given sequence of Is and Ds  import java.io.*; import java.util.*; public class GFG {  static void printLeast(String arr)  {  // min_avail represents the minimum number which is   // still available for inserting in the output vector.   // pos_of_I keeps track of the most recent index   // where 'I' was encountered w.r.t the output vector   int min_avail = 1, pos_of_I = 0;   //vector to store the output  ArrayList<Integer> al = new ArrayList<>();    // cover the base cases  if (arr.charAt(0) == 'I')   {   al.add(1);   al.add(2);   min_avail = 3;   pos_of_I = 1;   }   else  {  al.add(2);  al.add(1);  min_avail = 3;   pos_of_I = 0;   }  // Traverse rest of the input  for (int i = 1; i < arr.length(); i++)  {  if (arr.charAt(i) == 'I')  {  al.add(min_avail);  min_avail++;  pos_of_I = i + 1;  }  else  {  al.add(al.get(i));  for (int j = pos_of_I; j <= i; j++)  al.set(j, al.get(j) + 1);  min_avail++;  }  }  // print the number  for (int i = 0; i < al.size(); i++)  System.out.print(al.get(i) + " ");  System.out.println();  }  // Driver code  public static void main(String args[])  {  printLeast("IDID");   printLeast("I");   printLeast("DD");   printLeast("II");   printLeast("DIDI");   printLeast("IIDDD");   printLeast("DDIDDIID");   } } // This code is contributed by rachana soma 

# Python3 program to print minimum number # that can be formed from a given sequence # of Is and Ds  def printLeast(arr): # min_avail represents the minimum  # number which is still available  # for inserting in the output vector.  # pos_of_I keeps track of the most  # recent index where 'I' was  # encountered w.r.t the output vector  min_avail = 1 pos_of_I = 0 # Vector to store the output  v = [] # Cover the base cases  if (arr[0] == 'I'): v.append(1) v.append(2) min_avail = 3 pos_of_I = 1 else: v.append(2) v.append(1) min_avail = 3 pos_of_I = 0 # Traverse rest of the input  for i in range(1, len(arr)): if (arr[i] == 'I'): v.append(min_avail) min_avail += 1 pos_of_I = i + 1 else: v.append(v[i]) for j in range(pos_of_I, i + 1): v[j] += 1 min_avail += 1 # Print the number print(*v, sep = ' ') # Driver code printLeast("IDID") printLeast("I") printLeast("DD") printLeast("II") printLeast("DIDI") printLeast("IIDDD") printLeast("DDIDDIID") # This code is contributed by avanitrachhadiya2155 

// C# program to print minimum number that can be formed  // from a given sequence of Is and Ds  using System; using System.Collections.Generic;  class GFG  {   static void printLeast(String arr) {  // min_avail represents the minimum number which is   // still available for inserting in the output vector.   // pos_of_I keeps track of the most recent index   // where 'I' was encountered w.r.t the output vector   int min_avail = 1, pos_of_I = 0;   //vector to store the output  List<int> al = new List<int>();    // cover the base cases  if (arr[0] == 'I')   {   al.Add(1);   al.Add(2);   min_avail = 3;   pos_of_I = 1;   }   else  {  al.Add(2);  al.Add(1);  min_avail = 3;   pos_of_I = 0;   }  // Traverse rest of the input  for (int i = 1; i < arr.Length; i++)  {  if (arr[i] == 'I')  {  al.Add(min_avail);  min_avail++;  pos_of_I = i + 1;  }  else  {  al.Add(al[i]);  for (int j = pos_of_I; j <= i; j++)  al[j] = al[j] + 1;  min_avail++;  }  }  // print the number  for (int i = 0; i < al.Count; i++)  Console.Write(al[i] + " ");  Console.WriteLine(); } // Driver code public static void Main(String []args) {  printLeast("IDID");   printLeast("I");   printLeast("DD");   printLeast("II");   printLeast("DIDI");   printLeast("IIDDD");   printLeast("DDIDDIID");  } } // This code is contributed by Rajput-Ji 

<script>  // Javascript program to print   // minimum number that can be formed  // from a given sequence of Is and Ds    function printLeast(arr)  {  // min_avail represents the   // minimum number which is  // still available for inserting  // in the output vector.  // pos_of_I keeps track of the  // most recent index  // where 'I' was encountered   // w.r.t the output vector  let min_avail = 1, pos_of_I = 0;  //vector to store the output  let al = [];  // cover the base cases  if (arr[0] == 'I')  {  al.push(1);  al.push(2);  min_avail = 3;  pos_of_I = 1;  }  else  {  al.push(2);  al.push(1);  min_avail = 3;  pos_of_I = 0;  }  // Traverse rest of the input  for (let i = 1; i < arr.length; i++)  {  if (arr[i] == 'I')  {  al.push(min_avail);  min_avail++;  pos_of_I = i + 1;  }  else  {  al.push(al[i]);  for (let j = pos_of_I; j <= i; j++)  al[j] = al[j] + 1;  min_avail++;  }  }  // print the number  for (let i = 0; i < al.length; i++)  document.write(al[i] + " ");  document.write("</br>");  }    printLeast("IDID");  printLeast("I");  printLeast("DD");  printLeast("II");  printLeast("DIDI");  printLeast("IIDDD");  printLeast("DDIDDIID");   </script> 

1 3 2 5 4 1 2 3 2 1 1 2 3 2 1 4 3 5 1 2 6 5 4 3 3 2 1 6 5 4 7 9 8 

Time Complexity: O(N²) ,here N is length of string .
Auxiliary Space: O(N)  since N extra space has been taken.

This solution is suggested by Ashutosh Kumar.
 
Method 3 
We can that when we encounter I, we got numbers in increasing order but if we encounter 'D', we want to have numbers in decreasing order. Length of the output string is always one more than the input string. So the loop is from 0 to the length of the string. We have to take numbers from 1-9 so we always push (i+1) to our stack. Then we check what is the resulting character at the specified index.So, there will be two cases which are as follows:- 

Case 1: If we have encountered I or we are at the last character of input string, then pop from the stack and add it to the end of the output string until the stack gets empty. 

Case 2: If we have encountered D, then we want the numbers in decreasing order. so we just push (i+1) to our stack.

// C++ program to print minimum number that can be formed // from a given sequence of Is and Ds #include <bits/stdc++.h> using namespace std; // Function to decode the given sequence to construct // minimum number without repeated digits void PrintMinNumberForPattern(string seq) {  // result store output string  string result;  // create an empty stack of integers  stack<int> stk;  // run n+1 times where n is length of input sequence  for (int i = 0; i <= seq.length(); i++)  {  // push number i+1 into the stack  stk.push(i + 1);  // if all characters of the input sequence are  // processed or current character is 'I'  // (increasing)  if (i == seq.length() || seq[i] == 'I')  {  // run till stack is empty  while (!stk.empty())  {  // remove top element from the stack and  // add it to solution  result += to_string(stk.top());  result += " ";  stk.pop();  }  }  }  cout << result << endl; } // main function int main() {  PrintMinNumberForPattern("IDID");  PrintMinNumberForPattern("I");  PrintMinNumberForPattern("DD");  PrintMinNumberForPattern("II");  PrintMinNumberForPattern("DIDI");  PrintMinNumberForPattern("IIDDD");  PrintMinNumberForPattern("DDIDDIID");  return 0; } 

import java.util.Stack; // Java program to print minimum number that can be formed // from a given sequence of Is and Ds class GFG { // Function to decode the given sequence to construct // minimum number without repeated digits  static void PrintMinNumberForPattern(String seq) {  // result store output string  String result = "";  // create an empty stack of integers  Stack<Integer> stk = new Stack<Integer>();  // run n+1 times where n is length of input sequence  for (int i = 0; i <= seq.length(); i++) {  // push number i+1 into the stack  stk.push(i + 1);  // if all characters of the input sequence are  // processed or current character is 'I'  // (increasing)  if (i == seq.length() || seq.charAt(i) == 'I') {  // run till stack is empty  while (!stk.empty()) {  // remove top element from the stack and  // add it to solution  result += String.valueOf(stk.peek());  result += " ";  stk.pop();  }  }  }  System.out.println(result);  } // main function  public static void main(String[] args) {  PrintMinNumberForPattern("IDID");  PrintMinNumberForPattern("I");  PrintMinNumberForPattern("DD");  PrintMinNumberForPattern("II");  PrintMinNumberForPattern("DIDI");  PrintMinNumberForPattern("IIDDD");  PrintMinNumberForPattern("DDIDDIID");  } } // This code is contributed by PrinciRaj1992  

# Python3 program to print minimum  # number that can be formed from a # given sequence of Is and Ds  def PrintMinNumberForPattern(Strr): # Take a List to work as Stack stack = [] # String for storing result  res = '' # run n+1 times where n is length  # of input sequence, As length of # result string is always 1 greater for i in range(len(Strr) + 1): # Push number i+1 into the stack stack.append(i + 1) # If all characters of the input # sequence are processed or current # character is 'I  if (i == len(Strr) or Strr[i] == 'I'): # Run While Loop Until stack is empty while len(stack) > 0: # pop the element on top of stack  # And store it in result String res += str(stack.pop()) res += ' ' # Print the result print(res) # Driver Code PrintMinNumberForPattern("IDID") PrintMinNumberForPattern("I") PrintMinNumberForPattern("DD") PrintMinNumberForPattern("II") PrintMinNumberForPattern("DIDI") PrintMinNumberForPattern("IIDDD") PrintMinNumberForPattern("DDIDDIID") # This code is contributed by AyushManglani 

// C# program to print minimum number that can be formed // from a given sequence of Is and Ds using System; using System.Collections; public class GFG {   // Function to decode the given sequence to construct // minimum number without repeated digits  static void PrintMinNumberForPattern(String seq) {  // result store output string  String result = "";    // create an empty stack of integers  Stack stk = new Stack();    // run n+1 times where n is length of input sequence  for (int i = 0; i <= seq.Length; i++) {  // push number i+1 into the stack  stk.Push(i + 1);    // if all characters of the input sequence are  // processed or current character is 'I'  // (increasing)  if (i == seq.Length || seq[i] == 'I') {  // run till stack is empty  while (stk.Count!=0) {  // remove top element from the stack and  // add it to solution  result += String.Join("",stk.Peek());  result += " ";  stk.Pop();  }  }  }    Console.WriteLine(result);  }   // main function  public static void Main() {  PrintMinNumberForPattern("IDID");  PrintMinNumberForPattern("I");  PrintMinNumberForPattern("DD");  PrintMinNumberForPattern("II");  PrintMinNumberForPattern("DIDI");  PrintMinNumberForPattern("IIDDD");  PrintMinNumberForPattern("DDIDDIID");  } } // This code is contributed by 29AjayKumar 

<script>  // Javascript program to print  // minimum number that can be formed  // from a given sequence of Is and Ds    // Function to decode the given   // sequence to construct  // minimum number without repeated digits  function PrintMinNumberForPattern(seq)  {  // result store output string  let result = "";    // create an empty stack of integers  let stk = [];    // run n+1 times where n is length   // of input sequence  for (let i = 0; i <= seq.length; i++)   {  // push number i+1 into the stack  stk.push(i + 1);    // if all characters of the input   // sequence are  // processed or current character is 'I'  // (increasing)  if (i == seq.length || seq[i] == 'I')   {  // run till stack is empty  while (stk.length!=0) {  // remove top element from   // the stack and  // add it to solution  result +=   (stk[stk.length - 1]).toString();  result += " ";  stk.pop();  }  }  }    document.write(result + "</br>");  }    PrintMinNumberForPattern("IDID");  PrintMinNumberForPattern("I");  PrintMinNumberForPattern("DD");  PrintMinNumberForPattern("II");  PrintMinNumberForPattern("DIDI");  PrintMinNumberForPattern("IIDDD");  PrintMinNumberForPattern("DDIDDIID");   </script> 

1 3 2 5 4 1 2 3 2 1 1 2 3 2 1 4 3 5 1 2 6 5 4 3 3 2 1 6 5 4 7 9 8 

Time Complexity: O(n) 
Auxiliary Space: O(n),  since n extra space has been taken.
This method is contributed by Roshni Agarwal. 

Method 4 (Using two pointers) 
Observation 

1. Since we have to find a minimum number without repeating digits, maximum length of output can be 9 (using each 1-9 digits once)
2. Length of the output will be exactly one greater than input length.
3. The idea is to iterate over the string and do the following if current character is 'I' or string is ended. 
   
   1. Assign count in increasing order to each element from current-1 to the next left index of 'I' (or starting index is reached).
   2. Increase the count by 1.

Input : IDID Output : 13254 Input : I Output : 12 Input : DD Output : 321 Input : II Output : 123 Input : DIDI Output : 21435 Input : IIDDD Output : 126543 Input : DDIDDIID Output : 321654798

Below is the implementation of above approach:

// C++ program of above approach #include <bits/stdc++.h>  using namespace std;    // Returns minimum number made from given sequence without repeating digits  string getMinNumberForPattern(string seq)  {   int n = seq.length();  if (n >= 9)  return "-1";  string result(n+1, ' ');   int count = 1;   // The loop runs for each input character as well as   // one additional time for assigning rank to remaining characters  for (int i = 0; i <= n; i++)   {   if (i == n || seq[i] == 'I')  {  for (int j = i - 1 ; j >= -1 ; j--)  {  result[j + 1] = '0' + count++;  if(j >= 0 && seq[j] == 'I')  break;  }  }  }  return result; }   // main function  int main()  {  string inputs[] = {"IDID", "I", "DD", "II", "DIDI", "IIDDD", "DDIDDIID"};  for (string input : inputs)  {  cout << getMinNumberForPattern(input) << "\n";  }  return 0;  } 

// Java program of above approach import java.io.IOException; public class Test {  // Returns minimum number made from given sequence without repeating digits  static String getMinNumberForPattern(String seq)  {  int n = seq.length();  if (n >= 9)  return "-1";  char result[] = new char[n + 1];  int count = 1;  // The loop runs for each input character as well as   // one additional time for assigning rank to each remaining characters  for (int i = 0; i <= n; i++)  {  if (i == n || seq.charAt(i) == 'I')  {  for (int j = i - 1; j >= -1; j--)  {  result[j + 1] = (char) ((int) '0' + count++);  if (j >= 0 && seq.charAt(j) == 'I')  break;  }  }  }  return new String(result);  }    public static void main(String[] args) throws IOException  {  String inputs[] = { "IDID", "I", "DD", "II", "DIDI", "IIDDD", "DDIDDIID" };  for(String input : inputs)  {  System.out.println(getMinNumberForPattern(input));  }  } } 

# Python3 program of above approach # Returns minimum number made from  # given sequence without repeating digits  def getMinNumberForPattern(seq): n = len(seq) if (n >= 9): return "-1" result = [None] * (n + 1) count = 1 # The loop runs for each input character  # as well as one additional time for  # assigning rank to remaining characters for i in range(n + 1): if (i == n or seq[i] == 'I'): for j in range(i - 1, -2, -1): result[j + 1] = int('0' + str(count)) count += 1 if(j >= 0 and seq[j] == 'I'): break return result # Driver Code  if __name__ == '__main__': inputs = ["IDID", "I", "DD", "II", "DIDI", "IIDDD", "DDIDDIID"] for Input in inputs: print(*(getMinNumberForPattern(Input))) # This code is contributed by PranchalK 

// C# program of above approach  using System;  class GFG {    // Returns minimum number made from given // sequence without repeating digits  static String getMinNumberForPattern(String seq)  {   int n = seq.Length;   if (n >= 9)   return "-1";   char []result = new char[n + 1];   int count = 1;   // The loop runs for each input character  // as well as one additional time for  // assigning rank to each remaining characters   for (int i = 0; i <= n; i++)   {   if (i == n || seq[i] == 'I')   {   for (int j = i - 1; j >= -1; j--)   {   result[j + 1] = (char) ((int) '0' + count++);   if (j >= 0 && seq[j] == 'I')   break;   }   }   }   return new String(result);  }  // Driver Code public static void Main() {   String []inputs = { "IDID", "I", "DD", "II",   "DIDI", "IIDDD", "DDIDDIID" };   foreach(String input in inputs)   {   Console.WriteLine(getMinNumberForPattern(input));   }  }  }  // This code is contributed by Rajput-Ji 

<script>  // Javascript program of above approach    // Returns minimum number made from given  // sequence without repeating digits  function getMinNumberForPattern(seq)  {  let n = seq.length;  if (n >= 9)  return "-1";  let result = new Array(n + 1);  let count = 1;  // The loop runs for each input character  // as well as one additional time for  // assigning rank to each remaining characters  for (let i = 0; i <= n; i++)  {  if (i == n || seq[i] == 'I')  {  for (let j = i - 1; j >= -1; j--)  {  result[j + 1] =   String.fromCharCode('0'.charCodeAt() +   count++);  if (j >= 0 && seq[j] == 'I')  break;  }  }  }  return result.join("");  }    let inputs = [ "IDID", "I", "DD", "II", "DIDI",  "IIDDD", "DDIDDIID" ];    for(let input = 0; input < inputs.length; input++)  {  document.write(  getMinNumberForPattern(inputs[input]) + "</br>" );  } </script> 

13254 12 321 123 21435 126543 321654798

Time Complexity: O(N) 
Auxiliary Space: O(N), since N extra space has been taken.
This solution is suggested by Brij Desai.

Method 5 (Start with the Smallest)

Start with the smallest number as the answer and keep shifting the digits when we encounter a D. 
There is no need to traverse back for the index.
Follow the below steps,

1. Start with the smallest number for len(s)+1 (say for DI, start with "123")
2. Now, starting with the second digit (index 1) and first character (D), iterate until end of the digits list, keeping track of the first D in a sequence of Ds
   1. When we encounter a D
      move the digit at current index to the first D in the sequence
   2. When we encounter an I
      reset the last known location of D. Nothing to move as the digit is correctly placed (as of now...)

Below is the implementation of the above approach:

// c++ program to generate required sequence #include <iostream> #include <stdlib.h> #include <string> #include <vector> using namespace std; //:param s: a seq consisting only of 'D' and 'I' chars. D is //for decreasing and I for increasing :return: digits from //1-9 that fit the str. The number they represent should the min //such number vector<string> didi_seq_gen(string s) {  if (s.size() == 0)  return {};  vector<string> base_list = { "1" };  for (int i = 2; i < s.size() + 2; i++)  base_list.push_back(to_string(i));  int last_D = -1;  for (int i = 1; i < base_list.size(); i++) {  if (s[i - 1] == 'D') {  if (last_D < 0)  last_D = i - 1;  string v = base_list[i];  base_list.erase(base_list.begin() + i);  base_list.insert(base_list.begin() + last_D, v);  }  else  last_D = -1;  }  return base_list; } int main() {  vector<string> inputs  = { "IDID", "I", "DD", "II",  "DIDI", "IIDDD", "DDIDDIID" };  for (auto x : inputs) {  vector<string> ans = didi_seq_gen(x);  for (auto i : ans) {  cout << i;  }  cout << endl;  }  return 0; } 

// Java program to generate required sequence import java.util.*; public class Main {  public static void main(String[] args)  {  String[] inputs  = { "IDID", "I", "DD", "II",  "DIDI", "IIDDD", "DDIDDIID" };  for (String x : inputs) {  List<String> ans = didi_seq_gen(x);  for (String i : ans) {  System.out.print(i);  }  System.out.println();  }  }  //:param s: a seq consisting only of 'D' and 'I' chars.  //D is for decreasing and I for increasing :return:  // digits from 1-9 that fit the str. The number they represent  // should the min such number  public static List<String> didi_seq_gen(String s)  {  if (s.length() == 0)  return new ArrayList<>();  List<String> base_list  = new ArrayList<>(Arrays.asList("1"));  for (int i = 2; i < s.length() + 2; i++)  base_list.add(Integer.toString(i));  int last_D = -1;  for (int i = 1; i < base_list.size(); i++) {  if (s.charAt(i - 1) == 'D') {  if (last_D < 0)  last_D = i - 1;  String v = base_list.get(i);  base_list.remove(i);  base_list.add(last_D, v);  }  else {  last_D = -1;  }  }  return base_list;  } } // This code is contributed by Tapesh (tapeshdua420) 

# Python implementation of the above approach def didi_seq_gen(s: str):  '''  :param s: a seq consisting only of 'D'   and 'I' chars. D is for decreasing and   I for increasing  :return: digits from 1-9 that fit the str.   The number they represent should the min   such number  :rtype: str  example : for seq DII -> 2134  ''' if not s or len(s) <= 0: return "" base_list = ["1"] for i in range(1, len(s) + 1): base_list.append(f'{i + 1}') last_D = -1 for i in range(1, len(base_list)): if s[i - 1] == 'D': if last_D < 0: last_D = i - 1 v = base_list[i] del base_list[i] base_list.insert(last_D, v) else: last_D = -1 return base_list # Driver Code # Function call print(didi_seq_gen("IDID")) print(didi_seq_gen("I")) print(didi_seq_gen("DD")) print(didi_seq_gen("II")) print(didi_seq_gen("DIDI")) print(didi_seq_gen("IIDDD")) print(didi_seq_gen("DDIDDIID" ))