Decode the given sequence to construct minimum number without repeated digits

Given a sequence consisting of ‘I’ and ‘D’ where ‘I’ denotes increasing sequence and ‘D’ denotes the decreasing sequence. Decode the given sequence to construct minimum number without repeated digits.

 

For example,


sequence    output

IIDDIDID –> 125437698
IDIDII   –> 1325467
DDDD     –> 54321
IIII     –> 12345

 

 

The idea is very simple and effective. For each element of the given sequence, we insert its position (index+1) into a stack. If current character is increasing (‘I’) or if all characters of the input sequence are processed, we pop all numbers from the stack and append them to the output string.

C++

Download   Run Code

Java

Download   Run Code

Output:

Minimum number is 1325467

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
John
Guest

Is this correct? Output of DDI is 3214 when minimum would be 2134