What is the total number of distinct words that can be formed out of n letters using below operations with stack ?

Question

Suppose one character at a time comes as an input from a string of letters . There is an option either to

1) print the incoming letter or to

2) put the incoming letter onto stack .Also a letter from stack can be popped out at any time and printed .

The total number of distinct words that can be formed out of a string with n distinct letters is ?

Comments

@Deepanshu

Note that we need to push A,B,C in this order only.  While popping we print the letter.

1. Push A, Push B, Push C, Pop C, Pop B, Pop A. --> CBA

2.Push A, Push B, Pop B, Push C, Pop C, Pop A. --> BCA

3.Push A, Push B, Pop B, Pop A, Push C, Pop C.  --> BAC

4.Push A, Pop A, Push B, Pop B, Push C, Pop C. --> ABC

5.Push A, Pop A, Push B, Push C, Pop C, Pop B. --> ACB

Let us try to check if CAB is possible or not.  For this the pop order should be

Pop C, Pop A, Pop B

To Pop C we need to Push C before.

Push C,Pop C, Pop A, Pop B

To Pop A we need to Push A before popping and it should be pushed before C. So the only suitable position of Push A is before Push C.

Push A,Push C, Pop C, Pop A, Pop B

Now to Pop B it should be pushed before. It position should be b/w Push A and Push C to maintain the order. So,

Push A,Push B,Push C, Pop C, Pop A, Pop B

See the pushing sequence. C should be on the top of stack then B then A.

So after C is popped the top has B. But we are trying to pop A now which is not possible.

---

they are not saying about any order in which push pop occurs

---

MiNiPanda got it here in this question they have order here

Answer 1

I thing it will be n!

Comments

Any explanation ?