Last Updated on March 30, 2022 by Ria Pathak
Concepts Used:
Stack.
Difficulty Level:
Easy.
Problem Statement :
Make the minimum number without repetition of the digits such that it follows the sequence given in the string.
‘I’ represents increasing and ‘D’ represents decreasing.
See original problem statement here
Example:
Input:
1
IDIDI
Output:
132546
Explanation:
First index is I so in the output ,1 to 3 is increasing order.
The second index is D so in the output, 3 to 2 is decreasing order.
The third index is I so in the output, 2 to 5 is increasing order.and so on.OBSERVATION:
1.There can be atmost 9 digits in the output, as repetition is not allowed.
2.To form the minimum possible number, we must place the minimum possible digit at each index.
3.The output string contains one extra character than the input string, since the first character in the input string requires two characters.
Solving Approach:
1.Encountering ‘I’ demands us to increment the previous digit while for ‘D’ we need to decrement.
2.Traverse for i=0 to i=length of the input string and keep pushing (i+1) to the stack.
3.Following two cases arise for every index:
-
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.
Solutions:
#include <stdio.h>
void decode(char seq[],int n)
{
int stk[n+1];int top=-1;
for (int i = 0; i <= n; i++)
{
stk[++top]=(i + 1);
if (i == n || seq[i] == 'I')
{
while(top>=0)
{
printf("%d",stk[top]);
top--;
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
char seq[20005];
scanf("%s",seq);
decode(seq,strlen(seq));
printf("\n");
}
return 0;
}
#include <iostream>
#include <stack>
using namespace std;
// Function to decode the given sequence to construct minimum number
// without repeated digits
string decode(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());
stk.pop();
}
}
}
return result;
}
// main function
int main()
{
// input sequence
int t;
cin>>t;
while(t--){
string seq;
cin>>seq;
cout << decode(seq)<<endl;
}
return 0;
}
import java.io.*;
import java.io.*;
import java.util.*;
class prepbytes {
static void printLeast(String arr)
{
int min_avail = 1, pos_of_I = 0;
ArrayList<Integer> al = new ArrayList<>();
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;
}
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++;
}
}
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[])
{
Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
while(t-- >0 ){String str= sc.nextLine();
printLeast(str);
}
}
}
def decode(seq): stk = [] result = "" for i in range(len(seq)+1): stk.append(i + 1) if (i == len(seq) or seq[i] == 'I'): while(len(stk)): result += str(stk[-1]) stk.pop() return result for _ in range(int(input())): seq = input() print(decode(seq)) # your code goes here
[forminator_quiz id="1976"]
This article tried to discuss the concept of stack. Hope this blog helps you understand and solve the problem. To practice more problems on stack you can check out MYCODE | Competitive Programming.