When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

BiggestQuitter's blog

By BiggestQuitter, history, 6 years ago, In English

Hi guys, Can anyone please help me a bit in understanding this problem?

https://www.geeksforgeeks.org/number-subsequences-form-ai-bj-ck/

I m having difficulty in understanding mainly this part.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I am and will always be thankful to all people who have ever helped me and will help me in coming future.

Thank you from the bottom of my heart.

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

aCount is the number of subsequences of the letter 'a'.

Consider this example: aa. We can see that aCount for this is 3, because we can choose of these possibilities: (xa,ax,aa) (x means we did not use that character). Note also that this is independent of characters in between, i.e. the aCount of aa and ccbabbbcac are the same because both has exactly 2 a's.

Now, adding 1 a, we now have the following new subsequences: each of the old subsequences, each of the old subsequences + the new a, and the new letter a, alone. So a total of aCount + aCount + 1 subsequences.

Now, let's consider bCount, the number of subsequences with some a's and then some b's. in 'aab', we see that bCount should be 3 (axb,xab,aab), because it is just the number of ways we can choose subsequences of the first two a's, and then b. So every time we add a b, the number of ways increases by aCount.

Let's find bCount for 'aabb'. We have already determined that aab has 3 subsequences, so certainly we still have those. Additionally, we can add the new b onto any of these subsequences, to get 3 more. Finally, we have to count the subsequences that are made without using any other b's, and by the logic in the last paragraph, that is just aCount. So, bCount after this is just the old bCount*2 + aCount;

cCount is similar, and I think you can figure it out from here.