# Form minimum number from given sequence of D’s and I’s

INPUT :
DIDI

OUTPUT :
21435

### Example 2

INPUT :
DIDII

OUTPUT :
214356

In example 1, the given sequence is DIDI and the output number is 21435. For first letter “D” their is a decrement in number ie, 2 to 1. For second letter “I” their is an increment in number ie, from 1 to 4, similarly for other letters. One more possible answer for this sequence is 94856 , but we need the minimum number as the output. So, 94856 is the wrong answer.

From the given question we can conclude that, If the input sequence length is l then the output number length will be of length l+1 and maximum input sequence length can be of 8.

In this method, while traversing the array we will keep track of maximum digit and last printed digit that has encourted so far.

## Algorithm

1. Till the end of the array

case 1 :

If the element is I

a. Calculate the number of consecutive D’s that are present after the present element I and store it in noofDs variable.

b. If it is the first element, to print the first two elements in the output, make the maximum variable equal to number of consecutive D’s present plus 2 ie, max = noofDs + 2. Here, maximum variable keeps track of maximum digit till now. Print 1 and print maximim.

c. If it is not the first element, then make the maximum equal to previous maximum plus noofDs plus 1 ie, max = max + noofDs + 1 and make the last_printed equal to the maximum and print last_printed. Here last_printed keeps track of last printed digit.

case 2 :

If the element is D

a. If D is the first element in the sequence, calculate the number of consecutive D’s that are present after the present element D and store it in noofDs variable

b. Calculating the first digit to print based on no of D’s. So, make the maximum variable equal to number of consecutive D’s present plus 2 ie, max = noofDs + 2

c. First two digits in the output will be maximum and maximum -1 . Make the last_printed equal to maximum -1.

d. If it is not the first element, then decrement the last_printed and print the last_printed. ## C++ Program

```#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int minNumber(string arr)
{
int maximum = 0;
int last_printed = 0;
for (int i = 0; i < arr.length(); ++i)
{
int noofDs = 0;  //Number of D's that are present after the element
switch(arr[i])
{
case 'I':
{
int j = i+1;
while (arr[j] == 'D' && j < arr.length())
{
noofDs++;  //counting number of consecutive D's
j++;
}

if (i==0) //if it is the first element
{
maximum = noofDs + 2;

cout << " " << "1"; //print the first two elementss in the output
cout << " " << maximum;

// Set max digit reached
last_printed = maximum;
}
else
{
// If not first letter
maximum = maximum + noofDs + 1;

// Print digit for I
last_printed = maximum;
cout << " " << last_printed;
}

// For all next consecutive D's print the decrement sequence
for (int k=0; k<noofDs; k++)
{
cout << " " << --last_printed;
i++;
}
break;
}
case 'D':
{
if (i == 0)
{
// If 'D' is first letter in sequence
int j = i+1;
while (arr[j] == 'D' && j < arr.length())
{
noofDs++;
j++;
}

// Calculate first digit to print
maximum = noofDs + 2;

// Print the first two elements
cout << " " << maximum << " " << maximum - 1;

// Store last entry
last_printed = maximum - 1;
}
else
{
// If current 'D' is not first letter

// Decrement last_printed
cout << " " << last_printed - 1;
last_printed--;
}
break;
}

}

}
cout<<endl;
}
int main()
{
minNumber("DIDI");
return 0;
}```