In music, each note has a relative duration. For example, a whole note lasts four times longer than a quarter note. Half notes, eighth notes, and sixteenth notes have one half, one eighth, and one sixteenth the duration of whole notes, respectively.
A musical composition is characterized by its time signature, which defines the number of beats per measure. Time signatures
are written as fractions, where the numerator is the number of beats, and the denominator is the type of note represented by
each beat. For example, a time signature of 2/4 indicates that each measure contains two beats, each of which are quarter notes.
A time signature of 3/8 indicates that each measure contains three beats, each of which are eighth notes. For the purposes of
this problem, we will only consider the following time signatures: 3/8, 2/4, 3/4 and 4/4.
It is difficult for an untrained musician to determine the time signature of a composition. It is even more difficult
for a computer. You will be given a String duration containing the description of a composition. Each
character of duration corresponds to a single note in the composition. 'W' denotes a whole note, 'H' a half note, 'Q' a quarter note, 'E' an eighth note, and 'S' a sixteenth note.
Determine the time signature of the composition using the following heuristic algorithm (which is not very good, but quite simple):
- Consider all the available time signatures (3/8, 2/4, 3/4 and 4/4). Keep only the time signatures for which the composition would
contain an integral number of measures, and discard the rest.
- For each of the remaining time signatures, determine the number of notes in the composition that start and end in different measures. Keep only the time signatures for which this number is minimal.
- Select the smallest of the remaining time signatures (where 3/8 < 2/4 < 3/4 < 4/4).
Return the time signature as a String ("3/8", "2/4", "3/4", or "4/4"), or return "?/?" (quotes for clarity only) if there are no time signatures
left after step 1.