3
$\begingroup$

Given a sequence of two letters A and B find the total number of possible sub sequences where number of letter A is two times the number of letter B without changing the order.

For example consider the sequence AAAABBAAAA Now the possible sub sequences with given conditions can be AAB BAA AAAABB BBAAAA AAABBA AABBAA and ABBAAA.

Some insights on how to approach this problem would be great, with or without the solution. Also, I often come across these kind of problems where there's a bunch of permutations involved and you've to try them all to figure out the solution. Is there any specific approach for such questions? Any book you can recommend which can help me get better at solving such problem?

$\endgroup$
0
$\begingroup$

You ought to follow a algorithmic approach. Start off with the condition and and analyse the cases possible.

In your case the condition is No. of A's = 2 * No. of B's

So, B,s count in original string = 2;

Now if the string has > 4 A's you can have all cases otherwise you may have to reject cases that are not possible

(1 B, 2 A),(2 B, 4 A)                    ---- Similar approach needs to be followed for general case identification

so for the above two cases

case 1 : (1 B, 2 A)

no of permutations (p1) = fact(3)/fact (2) --- division by fact 2 to nullify the arrangement of identical A's

case 2 : (2 B, 4 A)

no of permutations (p2) = fact(6)/(fact(2)*fact(4))  --- division by fact to nullify arrangement of identical A's and B's

Now adding the answer form the two cases the final answer is

        total no of permutations = p1 + p2

                                 = 3 + 15 = 18

Hope this helps in general first you should always formulate the problem in to sections and parts and then find subparts along the way.

$\endgroup$
  • $\begingroup$ Thank you for your answer. But I was able to cook up this part myself as well. The answer for the given case is 7 and not 15. Since the order can't be changed, cases have to eliminated.That is what I wanted help with. $\endgroup$ – aandis Jul 8 '14 at 7:24
  • $\begingroup$ Not 18 I mean. Typo. $\endgroup$ – aandis Jul 8 '14 at 7:30
  • $\begingroup$ sorry i missed the without changing order part. i will try to post again to help you. $\endgroup$ – Ashwini Arvind Choudhary Jul 8 '14 at 7:39
  • $\begingroup$ I think we have to consider the BB part as a single unit and then permute. That way the permutations would be fact(5)/fact(4). But I am still missing a case $\endgroup$ – aandis Jul 8 '14 at 7:43
  • $\begingroup$ OK the other case is subtracting the repeated AABBAA which is identical. Just need to generalize this now. $\endgroup$ – aandis Jul 8 '14 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.