Hide

Problem B
ReMorse

Morse Code is an assignment of sequences of dots and dashes to alphabet characters. You are to create a Morse-like code that yields the shortest total length to a given message, and return that total length.

A dot symbol has length $1$. A dash symbol has length $3$. The gap between symbols within a character encoding has length $1$. The gap between character encodings has length $3$. Spaces, punctuation, and alphabetic case are ignored, so the text:

The quick brown dog jumps over the lazy fox.

is encoded as though it were just

THEQUICKBROWNDOGJUMPSOVERTHELAZYFOX

For example, with input ICPC, the answer is $17$: Encode the C’s with a single dot, the I with a dash, and the P with two dots, for an encoding of

$\bullet $ $\bullet \bullet $ $\bullet $

which has length

$(3)+3+(1)+3+(1+1+1)+3+(1) = 17$.
\includegraphics[width=0.5\textwidth ]{remorse.jpg}

Input

The single line of input contains a string $s$ ($1 \le |s| \le 32\, 000$) of upper-case or lower-case letters, spaces, commas, periods, exclamation points, and/or question marks. Everything but the letters should be ignored. The line will contain at least one letter.

Output

Output a single integer, which is the length of $s$ when encoded with an optimal reassignment of the sequences of Morse Code.

Sample Input 1 Sample Output 1
ICPC
17
Sample Input 2 Sample Output 2
A
1
Sample Input 3 Sample Output 3
The quick brown dog jumps over the lazy fox.
335

Please log in to submit a solution to this problem

Log in