Form Minimum Number from Given Sequence of D’s and I’s

Difficulty Level Easy
Frequently asked in Amazon Goldman Sachs
Array Stack StringViews 4388

Problem Statement

In the “Form Minimum Number from Given Sequence of D’s and I’s” problem, we have given a pattern containing only I’s and D’s. I for increasing and D for decreasing. Write a program to print the minimum number following that pattern. Digits from 1-9 and digits can’t repeat.

Input Format

The first and only one line containing a string “s”.

Output Format

Print the minimum number following that pattern. Digits from 1-9 and digits can’t repeat. If there is no way to print the desired output then print -1.

Constraints

  • 1<=n<=10^6
  • s[i] must be ‘D’ or ‘I’

Example

DIDI
21435
DIDIDIDIDIIIIIID
-1

In example 1, the given sequence is DIDI and the output number is 21435. For the first letter “D” there is a decrement in number ie, 2 to 1. For the second letter “I” there 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 the maximum input sequence length can be 8 if the answer is valid.

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

In example 2, the length is greater than 8 then there is no valid answer in this case. So we print -1.

Algorithm to Form Minimum Number from Given Sequence of D’s and I’s

1. Check the size of the given string. If it is greater than 8 then directly print -1 and return.

2. Start traversing given array char by char till the end of the array:

3. If the current element is ‘I’:

  • Calculate the number of consecutive D’s that are present after the present element I and store it in no of D’s variable.
  • If it is the first element, to print the first two elements in the output, make the maximum variable equal to the 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 maximum.
  • If it is not the first element, then make the maximum equal to the 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.

4. If the element is ‘D’:

  • 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 no of D’s variable.
  • 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
  • First, two digits in the output will be maximum and maximum -1. Make the last_printed equal to maximum -1.
  • If it is not the first element, then decrement the last_printed and print the last_printed.

Implementation

C++ Program to Form Minimum Number from Given Sequence of D’s and I’s

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

void printLeast(string s)
{
    if(s.length()>=9)
    {
        cout<<-1<<endl;
        return;
    }
  int start = 1, pos = 0;
  vector<int>v;
  if(s[0]=='I')
  {
    v.push_back(1);
    v.push_back(2);
    start = 3;
    pos = 1;
  }
  else
  {
    v.push_back(2);
    v.push_back(1);
    start = 3;
    pos = 0;
  }
  for (int i=1; i<s.length(); i++)
  {
    if (s[i]=='I')
    {
      v.push_back(start);
      start++;
      pos = i+1;
    }
    else
    {
      v.push_back(v[i]);
      for (int j=pos; j<=i; j++)
        v[j]++;
      start++;
    }
  }
  for(auto u: v)
  {
      cout<<u;
  }
  cout<<endl;
}

int main()
{
    string s;
    cin>>s;
  printLeast(s);
  return 0;
}

Java Program to Form Minimum Number from Given Sequence of D’s and I’s

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
       public static void print(String arr)
       {
              int start = 1, pos= 0;
              ArrayList<Integer> al = new ArrayList<>();
              if (arr.charAt(0) == 'I') 
              { 
                  al.add(1); 
                  al.add(2); 
                  start = 3; 
                  pos = 1; 
              } 
              else
              {
                  al.add(2);
                  al.add(1);
                  start = 3; 
                  pos = 0; 
              }
              for (int i = 1; i < arr.length(); i++)
              {
                   if (arr.charAt(i) == 'I')
                   {
                       al.add(start);
                       start++;
                       pos = i + 1;
                   }
                   else
                   {
                       al.add(al.get(i));
                       for (int j = pos; j <= i; j++)
                            al.set(j, al.get(j) + 1);
                       start++;
                   }
              }
              for (int i = 0; i < al.size(); i++)
                   System.out.print(al.get(i));
              System.out.println();
       }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        String s=sr.next();
        int n=s.length();
        if(n>8)
        {
            System.out.println(-1);
        }
        else
        {
            print(s);
        }
    }
}

DIIIDDDI
213487659

Complexity Analysis to Form Minimum Number from Given Sequence of D’s and I’s

Time Complexity

O(1) because for the length greater than 8 we directly print -1 otherwise find the answer in linear time which is O(10) around. So, overall complexity will be constant.

Space Complexity

O(1) because we don’t create too big auxiliary space. Here we use one vector whose worst-case size will be 10 only.

Translate »