Statistics

Problem Statement for "ColorfulCupcakesDivTwo"

Problem Statement

Beaver Bindu has N cupcakes. Each cupcake has one of three possible colors. In this problem we will represent the colors by uppercase letters 'A', 'B', and 'C'. Two cupcakes of the same color are indistinguishable. You are given a String cupcakes consisting of exactly N characters. Each character in cupcakes gives the color of one of Bindu's cupcakes.

Bindu has N friends, sitting around a round table. She wants to give each friend one of the cupcakes. Moreover, she does not want to give cupcakes of the same color to any pair of friends who sit next to each other.

Let X be the number of ways in which she can hand out the cupcakes to her friends. As X can be very large, compute and return the value (X modulo 1,000,000,007).

Definition

Class:
ColorfulCupcakesDivTwo
Method:
countArrangements
Parameters:
String
Returns:
int
Method signature:
int countArrangements(String cupcakes)
(be sure your method is public)

Notes

  • Formally, Bindu's friends can be labeled 0 through N-1 in such a way that friends i and (i+1 modulo N) are adjacent, for each i.

Constraints

  • cupcakes will contain between 3 and 50 characters, inclusive.
  • Each character in cupcakes will be either 'A', 'B', or 'C'.

Examples

  1. "ABAB"

    Returns: 2

    The two valid ways of handing out the cupcakes are "ABAB" and "BABA". (I.e., in the first way, friends 0 and 2 will receive cupcake of color A; and friends 1 and 3 will receive cupcake of color B. The second way is exactly opposite.)

  2. "ABABA"

    Returns: 0

    Regardless of how she hands out the cupcakes, there will always be a pair of adjacent friends who both received a cupcake of color A. Hence, there are no valid arrangements of cupcakes.

  3. "ABC"

    Returns: 6

    Each of the six permutations of "ABC" corresponds to a valid arrangement.

  4. "ABABABABABABABABABABABABABABABABABABABABABABABABAB"

    Returns: 2

  5. "BCBABBACBABABCCCCCAABBAACBBBBCBCAAA"

    Returns: 741380640

  6. "ABCCCACCCBCCC"

    Returns: 0

  7. "ABBBBAABAAACCBABAAACACCACABCABBAABCCCBAABCCBABA"

    Returns: 188207837

  8. "CAAABBAAB"

    Returns: 0

  9. "ACCACABACABABACBBCCCBAACABABA"

    Returns: 10664808

  10. "AABCACACAAABBBBBAABAACABCBAACABA"

    Returns: 16016

  11. "ABCABCABCC"

    Returns: 180

  12. "BBBBCACAAABABCB"

    Returns: 450

  13. "AACBAACBBCBBCBCACBCCCA"

    Returns: 174020

  14. "CBCAACCCACBCCBBBBABACCCACBBAAC"

    Returns: 8011080

  15. "BAACBABBABCC"

    Returns: 408

  16. "CCABABBBBBBAAAABCBCACBBCAAABBAAACBCACBBACABACACBB"

    Returns: 323466116

  17. "CBBCBCCBCACCBCBBAACCBCAACAACBACCBBCBAB"

    Returns: 19722697

  18. "CAACCAABBBABAACBBCBBBBAA"

    Returns: 185184

  19. "BCAACAAABACCBBABABBBACCCCBBBCCABAACABCACAABCAC"

    Returns: 198638319

  20. "ABABCBCCABBCABACCABCBCCBCBAC"

    Returns: 6825840

  21. "AABCBABCCBABACAAACCBCCABCABAABB"

    Returns: 85228176

  22. "BCBABAAACBAABAACACAACBCCCBCCCBC"

    Returns: 55045584

  23. "BAACBABBABBCCCBCCCACBCCABBAAAAACBACCBBBB"

    Returns: 680898127

  24. "AACCCAACBABBCBABCACAACCBCCABBC"

    Returns: 27054720

  25. "CCAABBACBBBBACBCCAABBABCBBBBBCCAAABBCBCCBABBAABAAB"

    Returns: 838553334

  26. "BCBABCCCCBABCACACAACABCBAABCBCACCAABAABCCBCCCCCCCA"

    Returns: 838553334

  27. "BACCCAABCCCABBAACCACCCABBACCACACAACCACBCBAABCCCCBA"

    Returns: 534612302

  28. "BABCAAAACACBAABACCACBACCCBBBBCBCBCCCACCAACCCAACACA"

    Returns: 451311121

  29. "CBACBCBCBCAAACAABBAAABACAABABBBBACACCACBACCABBCACC"

    Returns: 969866300

  30. "BABCAAACBCAABBACAACABAABBACAACAABACCBCBCCBABABABBA"

    Returns: 359261006

  31. "CABBCABCCCCCCAACABABBCACABABABCACABCCABBABBACCACBA"

    Returns: 807732686

  32. "ACACCBACCBBACBBAAABCCCBBAABABCBBACBCBCABABBAACBABA"

    Returns: 829127786

  33. "BAACBAAACBABBBCCAABBCAABAACCCAAAABAAAAACCBBBCAABCA"

    Returns: 612092993

  34. "CBAAABBCBBACCABCBBCABCCAAACCBBCBCACABBAAAAACBBBAAB"

    Returns: 823779011

  35. "ABCABAABCCCCBACBACABCABAAACBCCBCBAABABCBBCAAABCBAA"

    Returns: 969866300

  36. "AABCBCAABCBCACABACBBBAABBBABCBBACAABCBCBCABCBABCCA"

    Returns: 618020015

  37. "ABBBACCBACCCACAABCBBBBCBBBBABBABCCACCABAACAABBBABB"

    Returns: 439564296

  38. "CACCCBBACCCABCACBAABABAAABBBCAACBBCBCBBCABACAACCAA"

    Returns: 807732686

  39. "ABBACBACBCABACCCACACCBAAABACACCCBCCBACABABBAAAAABB"

    Returns: 618020015

  40. "CAAAAABCBACBCABCCCCABACCBAABBCACCAAABCAAACACABBCBB"

    Returns: 991666600

  41. "AABACCBABACBCCCAABABBAACAABCACBBCABABAACAACBABCBCC"

    Returns: 395853981

  42. "CCAACBAAABBCCBABBBBABABBBBAAAAACABAACBBCCCCCBABCBA"

    Returns: 270820324

  43. "CABACACAAAABCCCACBBABBAAACABCCCABBBABCBCCBAABAAACC"

    Returns: 618020015

  44. "CBAABBCAABCACACBBBAAACCCCACACCABAABCBBCCAACABACBBC"

    Returns: 823779011

  45. "ABCBCABBCABBACBABBCABAAABCCCABCCACBCABBCCCBAABC"

    Returns: 423411909

  46. "CBABBACBABABCCCCCAABBAACBBBBCBC"

    Returns: 24862992

  47. "AAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCC"

    Returns: 730747455

  48. "AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBACCCCCCCCCCCCCCCCB"

    Returns: 139077442

  49. "ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCCC"

    Returns: 726665879

  50. "AAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCABCAB"

    Returns: 139077442

  51. "ABCA"

    Returns: 4

  52. "ABCCCAAABBBCCCAAABBBCBCBACBACACACACBCACBCBAC"

    Returns: 280387198

  53. "BCBABBACBABABCCCCCAABBAACBBBBCBCAAABBC"

    Returns: 886239205

  54. "AAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCC"

    Returns: 395853981

  55. "AABABABABABABCCCBBCBABCBACBACBBCBCCBCCCBACABCBCBC"

    Returns: 521301082

  56. "AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCC"

    Returns: 853062226

  57. "ACBACBABBCABCBABABACACABCBACBACBABCAC"

    Returns: 746183318

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: