Statistics

Problem Statement for "MusicLicenses"

Problem Statement

A popular on-line music service allows customers to play their music on up to three different computers, each of which must have a license. A license can be transferred from one computer to another, but it cannot be transferred back. In other words, once a computer has lost its license, it can never acquire a new one.

You are auditing customer access records, trying to detect fraud. You have a log of the computers a particular customer has used to play music, and you want to know whether she has done so legally. Each different computer is identified by a single uppercase letter ('A'-'Z'). The String log contains a sequence of these letters. For example, "ABCBAD" means that the customer has played a total of six songs on four distinct computers, with the first song played on computer 'A' and the last song played on computer 'D'. You do not know which computers had licenses at which times, but you can infer that the customer must have transferred a license to computer 'D' sometime after the third song and before the sixth song.

You want to detect when a customer's log could not have happened legally, no matter how she managed her licenses. For example, there is no legal way to produce the log "ABCDABCD": The customer can only play the first song on computer 'D' by transferring a license from one of the other computers, so one of the three subsequent songs will be played on a computer that has lost its license. When you have detected fraud, you are to return the zero-based index of the first song that proves that fraud occurred. In this case, you would return 6, the index of the second 'C', because the prefix "ABCDAB" could have been produced legally but "ABCDABC" could not. (Note that this does not necessarily mean that the 'C' access itself is illegal because the illegal access might have occurred earlier.)

If the log does not prove fraud, return -1.

Definition

Class:
MusicLicenses
Method:
audit
Parameters:
String
Returns:
int
Method signature:
int audit(String log)
(be sure your method is public)

Constraints

  • log contains between 1 and 50 characters, inclusive.
  • Each character in log is an uppercase letter ('A'-'Z').

Examples

  1. "ABCBAD"

    Returns: -1

    The first example above. No fraud has been detected.

  2. "ABCDABCD"

    Returns: 6

    The second example above. The prefix "ABCDAB" could have been produced legally but "ABCDABC" could not.

  3. "X"

    Returns: -1

  4. "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    Returns: -1

  5. "AVERYUNUSUALACCESSPATTERNINDEED"

    Returns: 15

  6. "Q"

    Returns: -1

  7. "AZ"

    Returns: -1

  8. "JKL"

    Returns: -1

  9. "JKLJKLJKLJKLJKLJKLJKLJKLJKLJKLJKLJKL"

    Returns: -1

  10. "FOURSCOREANDSEVENYEARS"

    Returns: 12

  11. "TWASBRILLIGANDTHESLYTHYTOVES"

    Returns: 14

  12. "ALLMIMSYWERETHEBOROGOVES"

    Returns: 23

  13. "AAAAAAAAAABBBBBBBBBBAAAAAAAAAACCCCCCCCCCAAAADCCBBA"

    Returns: 49

  14. "TISAGIFTTOBESIMPLE"

    Returns: 12

  15. "MYFAVORITEPIZZATOPPINGISSAUSAGE"

    Returns: 15

  16. "HAWHAURYEGAUNYECROWLINFERLIE"

    Returns: 13

  17. "LOOKUPONMYWORKSYEMIGHTYANDDESPAIR"

    Returns: 15

  18. "NOWISTHEWINTEROFOURDISCONTENT"

    Returns: 10

  19. "THEQUICKBROWNFOXJUMPEDOVERALAZYDOG"

    Returns: 20

  20. "ICHINISANSHIGOROKU"

    Returns: 10

  21. "SYZYGYQUICKTROPICALHEXAXE"

    Returns: -1

  22. "DIJKSTRAKNUTHCOOK"

    Returns: -1

  23. "ABCDEFGHIJIHGFEDCBA"

    Returns: 12

  24. "PEONZSGPBRXCYHYUTSQJKHWFDSMFXQI"

    Returns: 28

  25. "GPRJWGQUMDONPVGLPEZWTQPKGIVZMYABEJXCSO"

    Returns: 19

  26. "BEBHPYRFHPHAPMRZQQCHOSHYBGWCKKTDF"

    Returns: 14

  27. "BGMFPYV"

    Returns: -1

  28. "SPHAIQGJGMTEGIYOSHFWCIHIMFNQGEGIGDBMCT"

    Returns: 16

  29. "OJUGBQZWQGOQPAMJRMEHGJOC"

    Returns: 10

  30. "VCAGZEQEZMKCAOYUCGJWTUFANXFSNVIMRGLWPAPBJJQXQRZF"

    Returns: 11

  31. "BNLQTYUOGEWHVIVVJCP"

    Returns: -1

  32. "IHLXLBQKKJSJALICOGOHLIRXRATJAQI"

    Returns: 14

  33. "RDKRMAGPG"

    Returns: -1

  34. "FLROYBJZISBUGTJSLZNUJFCAFTWE"

    Returns: 16

  35. "MJOPGFRNYDDIYGHUO"

    Returns: 16

  36. "MVXFHLBGHHPEXCOVFSA"

    Returns: 15

  37. "AWWQQLJRBWPKNFT"

    Returns: -1

  38. "GLOUFAKMWKGLUKNHCENPQZHCDHZIHBGFMNIF"

    Returns: 11

  39. "YWRIMKCLYLGYTKECVQSVELCZUWDBDQKBAABAUJMMGYBPMIWWFK"

    Returns: 15

  40. "OEJPWNPVSKLGKHMVPKACJTRQTLXECVWUEFYBZQUPY"

    Returns: 16

  41. "YMZVEXTVTGETFTDXYZKIDIULJXO"

    Returns: 15

  42. "LLPECGQWRXTYFZYQTOJVGBEFRDVUWOUOHXZFBPZYHBMZ"

    Returns: 16

  43. "KJVFPLVSYFSMLRHOHNUYPXLQNLOULBQZIDZFMZFYHPFUIRR"

    Returns: 12

  44. "RXCUXDZEDSXKTXTHDKGNPNMDBKTREEXEXOCKGSIRTCN"

    Returns: 17

  45. "XAQYAKAPLSFCWEECHRCTMDNYBJEZGJQETTVWGQIKRU"

    Returns: 26

  46. "NOHRUPPACXKPCSHLVAKJWVIDPEOYMHEIBYWGQUCRLFOY"

    Returns: 14

  47. "IXMFBXYHDHDTKMCHYZCYVTHKG"

    Returns: 16

  48. "FNOZZO"

    Returns: -1

  49. "RCRIRTJTGDSUUVMMCKXMWHAADFVBPOZSIQJYZAMBJHHF"

    Returns: 26

  50. "WVHJQXPBCETBYBWBWUVTEPSSBRIDIYW"

    Returns: 18

  51. "XXEXNHDSFDL"

    Returns: -1

  52. "JUCHLVJQYZLL"

    Returns: -1

  53. "SAOBTOFGMBPMIIUPGZDQXVMLOAOPX"

    Returns: 22

  54. "IFTKLHRMLEWRKFYJCEITLVIYTHLWVJBGMSDVZKDAAQGMNEFESY"

    Returns: 12

  55. "AQBUXTMWVXRUXJFSXOIJCUIUGLAMWDPFMDFU"

    Returns: 21

  56. "BQQNNQOBDKWDFCMXTYSJUWJSAQQAPGBUZNHAGIPLYN"

    Returns: 23

  57. "CJRHGKOEVLNUZXVZEYELBEAZIUOGKNPEMFVJ"

    Returns: 16

  58. "FBEGTJBUTVUGXRWBKL"

    Returns: 11

  59. "DJMALOMYZUSEPG"

    Returns: -1

  60. "DMVYJCLLTUBQAENV"

    Returns: -1

  61. "XNDLIBAOVVZRSVFSWAQLCTILS"

    Returns: 19

  62. "WAMDAOIFDQKSSCO"

    Returns: -1

  63. "JZTOCY"

    Returns: -1

  64. "GTSBHZSCAJUWACISSVEYBRDYOJQA"

    Returns: 15

  65. "LXLMVGYINCGDRCMNGREAKULBFEFZJZWNZBRJJSIBIXSTPR"

    Returns: 15

  66. "KLWQDOAZNYTFDJXZ"

    Returns: -1

  67. "TEOOTXKQAINOSY"

    Returns: -1

  68. "JBMXKSZIDOQQHSKPSPBJKMHCUQDHBIKOWSSKJK"

    Returns: 18

  69. "HKSOZWDHXIFPMWTTNZVSJFWSGXLLPHHTLXDOSYKPGUYLKOKGFB"

    Returns: 17

  70. "EHJJYDTKGBZZFJQRM"

    Returns: -1

  71. "AJKLOLZEJRUPXKHHG"

    Returns: 13

  72. "NEIVMXBGNGQWAXNWLNMULIILOPHWCMOCOVO"

    Returns: 15

  73. "JXUOWGZRMQKHNPKBZUIDXCRWXCYNJOFXBZLNKXI"

    Returns: 17

  74. "ABCDABC"

    Returns: 6

  75. "ABCDABD"

    Returns: -1

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: