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.
|