Samir String

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 in data structures in java:

  1. 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.

  2. 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);  
        } 
    }   
 }
Previous post Detect Cycle
Next post Max Rectangle

Leave a Reply

Your email address will not be published. Required fields are marked *