'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before', 'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity', 'Knowing how to code is a major requirement for astronomers', 'The first computer didn’t use any electricity', 'Do you know there is a coding language named “Go“', 'Computer programming is one of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the name of the first programming language', 'The first programmer was the daughter of a mad poet', 'Many programming languages share the same structure', 'Coding will soon be as important as reading', 'How many programmers does it take to change a light bulb? None, that’s a hardware problem', 'Why do Java developers wear glasses? Because they can’t C', 'Software and temples are much the same — first we build them, then we pray', 'An engineer will not call it a bug — it’s an undocumented feature', 'In a room full of top software designers, if two agree on the same thing, that’s a majority', 'C programmers never die. They are just cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java', 'The best thing about a boolean is even if you are wrong, you are only off by a bit', 'Linux is only free if your time has no value', 'The computer was born to solve problems that did not exist before',
Update appNew update is available. Click here to update.
Last Updated: 27 Feb, 2021

Number following a pattern

Hard
Asked in companies
Goldman SachsJosh Technology Group

Problem statement

You are given a string 'S' that consists of I’s and D’s pattern only. 'I' is for increasing, and 'D' is for decreasing. Your task is to return the string that consists of a minimum number following that pattern.

Note:

1) Digits of the number should be in the range [1,9] and can’t repeat.

2) The length of the string should be less than or equal to 8.
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases. 

The first line of each test case contains a string 'S', as described in the problem statement.
Output Format:
For each test case, return a string consisting of a minimum number following the given pattern.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10^3
1 <= |S| <= 8

where |S| is the length of the given string.
Time Limit: 1sec

Approaches

01 Approach

  • Create an empty stack and a string 'ANS' for storing the result.
  • In stack, we are going to push i+1every time for all 0 <= ‘i’ < |S| when we are traversing the string ‘S’.
  • The main observation is that:
    • The length of the output string is always one more than the input string. So, we are going to start the loop from ‘i’ = 0 to ‘i’ <= S.length().
    • When we encounter a D, we need numbers in decreasing order, so we just push ‘i+1’ because in the future, when we are going to empty the stack, we are having all the numbers in decreasing order beforehand.
    • When we encounter an I at the ith index of the string ‘S’, we need numbers in increasing order. Since every time we are pushing ‘i+1’ in the stack, we first push ‘i+1’, and also we have to empty the stack whenever we are facing an I. So, 2 cases are possible:
      • If S[i-1] is equal to “D”, we want numbers in the decreasing order, and the stack contains numbers in the decreasing order itself. So, just pop the element, add it into the 'ANS' string until the stack becomes empty.
      • If S[i-1] is equal to “I”, the stack only contains ‘i+1’ since the stack is already empty in the (i-1)th index because it is I. So, just add the top element in the 'ANS' string and pop that element which implies stack again become empty.
    • When we are at the last of the string, just pop the element and add it into the 'ANS' string until the stack becomes empty.
  • Combing all the observations in the code, run a loop from i=0 to ‘i’<=|S|, in each iteration:
    • Push ‘i+1’ in the stack.
    • If S[i] == ‘I’ or ‘i’ == S.length(), then pop the element, add it into the string 'ANS' till the stack becomes empty.
  • Return the string 'ANS'.