Statistics

Problem Statement for "CircleCount"

Problem Statement

We have a circular track on which a number of loaded cars are located. Each car has its own specified unloading position along the track. The cars can be moved in either direction along the track, but cannot pass each other.

We want to make a worklist, specifying the order in which the cars should be moved. The order of cars in the worklist must allow each car to be moved just once all the way to its unloading position. How many different orders will allow this?

The cars are each named with a lowercase letter, and their destinations with the same letter but in uppercase. The positions of the cars and of their destinations are given by a sequence of letters that is regarded as circular by wrapping around the ends. So, for example, "BACacb" describes a situation in which going clockwise around the track we encounter B, A, C, a, c, b, and then return back to B. Here there are 3 different orders in which the cars can be moved to their destinations: a then c then b, a then b then c, or b then a then c.

Given the original positions of the cars and destinations in a String circle, return the number of different orders in which the cars can be moved. If there are more than 2,000,000,000 orders return -1. If no order is possible, your method should return 0.

Definition

Class:
CircleCount
Method:
countOrder
Parameters:
String
Returns:
int
Method signature:
int countOrder(String circle)
(be sure your method is public)

Constraints

  • circle will contain between 2 and 50 characters, inclusive.
  • Each character will be a letter ('a'-'z', 'A'-'Z').
  • No character will appear more than once in circle.
  • If a letter appears in circle, it will appear both in uppercase and in lowercase.

Examples

  1. "BACacb"

    Returns: 3

    This is the example given above.

  2. "ABCacb"

    Returns: 0

    We cannot move c first. If we move a first, then we can never move b to B, but if we move b first we can never move a to A.

  3. "xX"

    Returns: 1

    We must move car x. We could move it to its destination either in a clockwise or a counterclockwise direction but there is only one order for choosing the cars to move.

  4. "ABCabc"

    Returns: 2

    The possibilities are 1) a then b then c, or 2) c then b then a (moving the cars in the other direction).

  5. "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPp"

    Returns: -1

    These 16 cars can be move in any order, so there are 16! orders which is greater than 2,000,000,000

  6. "eAEBDbFdfcgCGa"

    Returns: 210

  7. "BACacbYXZxzy"

    Returns: 0

    //String circle = "BACacbYXZxzy"; //should be 0 //String circle = "BACacb"; //3 //String circle = "XYxPyp"; //1 //String circle = "pXYPxy"; // 2 //String circle = "pP"; // 1 //String circle = "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpP"; // -1 String circle = "ZYACBacbxzyX"; //20=10+10= [CBcbxzyXZY + [ACBacbxzXZ

  8. "XYxPyp"

    Returns: 1

  9. "pXYPxy"

    Returns: 2

  10. "ZYACBacbxzyX"

    Returns: 20

  11. "abcdABCDefgEFGHIhJijKkLMlm"

    Returns: 3603600

  12. "Aa"

    Returns: 1

  13. "AazZyYBbcCdDgGiIOoPpEesS"

    Returns: 479001600

  14. "AazZyYBbcCdDgGiIOoPpEesSrR"

    Returns: -1

  15. "rRzZ"

    Returns: 2

  16. "gQGq"

    Returns: 2

  17. "TRrgGt"

    Returns: 6

  18. "hLHjlVJv"

    Returns: 0

  19. "vHWRhwVr"

    Returns: 1

  20. "nvayNVAY"

    Returns: 2

  21. "ZxXrnRzN"

    Returns: 4

  22. "ufeaEAUF"

    Returns: 6

  23. "qoeOEnNQ"

    Returns: 12

  24. "wWvVmMzZ"

    Returns: 24

  25. "dDzZRftFrT"

    Returns: 0

  26. "dnDocNOiCI"

    Returns: 1

  27. "DOocCspdSP"

    Returns: 20

  28. "pPoOLlBXbx"

    Returns: 60

  29. "mUuVBvbHMh"

    Returns: 30

  30. "GnNzvZiVgI"

    Returns: 5

  31. "XSOknKNxso"

    Returns: 10

  32. "xnKGDXNkgd"

    Returns: 2

  33. "lQqaAwWEeL"

    Returns: 120

  34. "LlkKeEqQyYwW"

    Returns: 720

  35. "kbjqBmJQpMzPZK"

    Returns: 7

  36. "dwoPQvnpqFDWOfVN"

    Returns: 1

  37. "gSpGyPYBbjJUuwWRrs"

    Returns: 15120

  38. "xwkWKPGZpDgHRzdhNrnX"

    Returns: 360

  39. "xSdvXDkwVKWlhLHEGJegjs"

    Returns: 4620

  40. "NGkbcESlVPMKjBCLJxhXHtiwuTIarzoWfUAdyRngeZsOFDvpYm"

    Returns: 300

  41. "utMdhOBlpnmobaevsAEfqVSFxQXiIYWCJZRGUTyDHwLPcjzNrg"

    Returns: 8652600

  42. "nSXgtEqcsxebBAaYOHRZULWVyMJPKDIohrzuNGlwvTmjQpkCdi"

    Returns: 600

  43. "YJNVLUDXsIMTSHhkKQEqewpcorbafWzyPjCnOvlRBudxAimtFZ"

    Returns: 151800

  44. "vZbNgznkKXYUIWMxyuLSDiwmlsdtTQEqPReHprFhCJfOcjVBGo"

    Returns: 490314000

  45. "DyKjYxJbXBFQEVOfqeGCvIMogUcAiWSPNmuawsLpnltTZzRrdk"

    Returns: 1029659400

  46. "ksFuxfqQoOHhpPiIzjZJMGTAmNCEVgLRBtaDYncevKlSrbUdXy"

    Returns: 1211364000

  47. "SmMKOWGkowPVgRDpQNvrLJUZdqnHBXljuzhbxtTaAEIeFiCfcs"

    Returns: 1817046000

  48. "huwaNHUysWAYSFEfGegIiJPTXQjZpCMOBLVtxqzDcmobRlvdrn"

    Returns: -1

    Total count is 5883768000.

  49. "ZhNQKUHITYBiXtPyJOAbRxDSpjoWardswvmVMCcgelznGEqLku"

    Returns: -1

    Total count is 3432198000.

  50. "UWTPjbfCZXyuwtKOVpcNzxkovMnmRrhHDdlLsSGgQqEIJBeFiY"

    Returns: -1

    Total count is 2422728000.

  51. "QPwEdGjCsqpMUegIFcmuAifaxtXvobTyVrOBYRZzNnlLKWDkJS"

    Returns: -1

    Total count is 2353507200.

  52. "DylGKpqMenRYLPQvENVXCAOHxZScaohzWswutUTBbijIdgJkmr"

    Returns: -1

    Total count is 2206413000.

  53. "ntxTgXGdDyYzZQqjrJROoVNv"

    Returns: 19958400

  54. "eHhJjdDQRqXrxKkyYwWNCnczZE"

    Returns: 518918400

  55. "igGaAnNoOzZdDPpTtFfRrkjKJI"

    Returns: -1

  56. "HYQIAiaeEGgUulLFDZfdzMmNnhyq"

    Returns: 1210809600

  57. "yYmijpMhIJPHdDBbsSaekoAEKOQqlL"

    Returns: 454053600

  58. "jLMJDdYyOoNEnZAWezBRawbrufUvlFVm"

    Returns: 5765760

  59. "yXKOZNuYdjUafDJAFSEQHseqGhgtxkoTzn"

    Returns: 6188

  60. "phkyXuzxrvRVMmnNbgBGJjLlTQDtSOqCPdHsKYUoZc"

    Returns: -1

    Total count is 2051179200.

  61. "GneklgCMcIZPmHiXzphxwouWOUrRsSVDBNvEKdbL"

    Returns: 1995364800

  62. "iVdvtTZznbNmphBjwMPHJWGgaAXRQUIxDrqu"

    Returns: 252046080

  63. "AounFlekafcgimCGIbMBZYzyhrHRWQOwUNqLEK"

    Returns: 69837768

  64. "DwcuzYgWmCUZGoMaOAIisSNFPXnfpVxvlbqLBQdy"

    Returns: 931170240

  65. "ADTVMlaFdtvNmfnPpsySiwYhqozIWHbQOkZBKERerL"

    Returns: 174594420

  66. "aNEQdfjXneqxbBVvpPhsrHmkSiyRMKIYGOUTgoADFutJ"

    Returns: 465585120

  67. "ZHxXEYKFTBRNeyVkIftbrnvPSWipOswoamAqMjQJlcLzCh"

    Returns: 514829700

  68. "rtyJBkXIlVdUHzmQajbxiCvuhqcWOSNwGoERTYKLDZsngeMA"

    Returns: 1

  69. "rFstfMKmPQUkDNLpqudnCZIlcziebEBhoaHjOAJxXYyVvgGRST"

    Returns: -1

  70. "RJjYLyZlEWzewagqAGkQKMSmsdDXxfFIiCOcobpBrP"

    Returns: -1

  71. "TWaZAOGoSgYsyqQMmdDrRxkXjpKJPBUbuvVlinfLIctNwzFC"

    Returns: -1

  72. "RFPIJUijuBbnvNhVHaASEGseYgyczCoZOlLDXdxwtqrWfpTQ"

    Returns: -1

  73. "TxhNtnwWZzEecCsrgSfRGFQBqbaAyYjilJILDdUuopOmPMKXHk"

    Returns: -1

  74. "LtjrOloNnpyPYKkwWGgHheEVvAUauxXmMDdfFZzcqCbQBTJR"

    Returns: -1

  75. "bcusSfmFMvVQqlkLKiIoOnNeEGgaAxXjJPpRrHYhTyDtdBCU"

    Returns: -1

  76. "rfXTJdAWBMcHRFDCOoknKyvigxtjNaYwbVmGhI"

    Returns: 0

  77. "IuDNUiydnY"

    Returns: 0

  78. "BxtjTKdXHGJDgvbkVh"

    Returns: 0

  79. "xcjhYUCyJDKIGLgQRPrqXdilHpuk"

    Returns: 0

  80. "rCubjdAvyzcaIOioEemMqQHXLSPKWNGhFxlspRkgwBJDnVYUZf"

    Returns: 0

  81. "ABCabcDEFdefGHZghz"

    Returns: 1680

  82. "mMuUgGiIsSrRcCaAoOkKbBqQvVwWeEpPZXhjzxHJtTdDlL"

    Returns: 0

  83. "aBAbcCdefDEFghijGHIJklKLPQpq"

    Returns: 0

  84. "bcaCBADdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYy"

    Returns: 0

  85. "ghijklMNOPQRSTUVXYZmnopqrstuvxyzABCDEFGHIJKLabcdef"

    Returns: 5200300

  86. "ABCabcDdEeFfGgHhIiJjKkLlMm"

    Returns: 1037836800

  87. "EeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuWwXxYyZzAbCaBcDd"

    Returns: 0

  88. "VXvxZYzyijIJaABbcCdDEefFgGhHKklLmMopOPqQrRsStuTU"

    Returns: -1

  89. "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWyXxY"

    Returns: 0

  90. "AaBCbcdD"

    Returns: 12

  91. "ZzCcVvBbNnMmAaSsDdFfGgHhJjKkLlQqWwEeRrTtYyUuPOIpio"

    Returns: 0

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: