153 - Permalex
Solution Description : Mathematical (permutation) problem If you generate all permutation of given string then you got TL, You can easily solve this problem using the formula : n! / (r1! * r2! * r3!...) Here n = total character, r1, r2, r3..= number of repeated character. Suppose aabbbc, n=6, r1=2, r2=3 Example: Input: dcaba 1. For string dcaba. Take the first character d, find all characters are less than d. Here the characters are a, b, c. For character a, you can find 24 possible arrangement. Because without a the string is: dcba so, 4! = 24. For character b, you can find 12 possible arrangement. Because without b the string is: dcaa so, 4! / 2! = 12. For character c, you can find 12 possible arrangement. Because without c the string is: daba so, 4! / 2! = 12. Then remove the first character from "dcaba". You got "caba". 2. For string caba. Take the first character c, find all characters are less than c. Here the characters are a, b. For character a, you can find 6 possible arrangement. Because without a the string is: cba so, 3! = 6. For character b, you can find 3 possible arrangement. Because without b the string is: caa so, 3! / 2! = 3. Then remove the first character from "caba". You got "aba" 3. For string aba. Take the first character a, find all characters are less than a. Here no character found. Then remove the first character from "aba". You got "ba" 4. For string ba. Take the first character b, find all character are less than b. Here the character is a. For character a, you can find 1 possible arrangement. Because without a the string is: b so, 1! = 1. Remove the first character from "ba". You got "a". Do not need to do anything for that. Total arrangement: 24 + 12 + 12 + 6 + 3 + 1 = 58 So, 58 possible arrangement before come "dcaba". "dcaba" is the 59th arrangement. You can do this recursively. |
||||||||||
103 - Stacking Boxes