{"id":1973,"date":"2020-07-01T09:46:54","date_gmt":"2020-07-01T09:46:54","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1973"},"modified":"2022-03-30T22:15:13","modified_gmt":"2022-03-30T22:15:13","slug":"samir-string","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/samir-string\/","title":{"rendered":"Samir String"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used:<\/h3>\n
\n

Stack.<\/p>\n<\/blockquote>\n

Difficulty Level:<\/h3>\n
\n

Easy.<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Make the minimum number without repetition of the digits such that it follows the sequence given in the string.
\n‘I’ represents increasing and ‘D’ represents decreasing.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Example:<\/h4>\n
Input:\n1\nIDIDI\n\nOutput:\n132546\n\nExplanation:\nFirst index is I so in the output ,1 to 3 is increasing order.\nThe second index is D so in the output, 3 to 2 is decreasing order.\nThe third index is I so in the output, 2 to 5 is increasing order.and so on.<\/code><\/pre>\n
OBSERVATION:<\/h4>\n
\n
1.There can be atmost 9 digits in the output, as repetition is not allowed.<\/p>\n
2.To form the minimum possible number, we must place the minimum possible digit at each index.<\/p>\n
3.The output string contains one extra character than the input string, since the first character in the input string requires two characters.<\/p>\n<\/blockquote>\n
Solving Approach:<\/h4>\n
\n
1.Encountering ‘I’ demands us to increment the previous digit while for ‘D’ we need to decrement.<\/p>\n
2.Traverse for i=0 to i=length of the input string and keep pushing (i+1) to the stack.<\/p>\n
3.Following two cases arise for every index:<\/p>\n<\/blockquote>\n
    \n
  • \n
    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.<\/p>\n<\/li>\n
  • \n
    Case 2: If we have encountered D, then we want the numbers in decreasing order. So we just push (i+1) to our stack.<\/p>\n<\/li>\n<\/ul>\n
    Solutions:<\/h3>\n\t\t\t\t\t\t