Vim

문제

Ernest Vincent Wright was an American author, known for writing a novel (Gadsby) without using the letter “e”. Victor is a big fan of Ernest and tries to imitate him in writing a novel, but is looking for a real challenge. He uses only the first ten characters of the alphabet (namely abcdefghij). Ironically, the “e” key on his computer breaks halfway through the novel, and for consistency, he decides to delete all the “e”s he has already written. His friend, a programmer, recommended him to use the text editor Vim to perform this task. Unfortunately, Victor is not very familiar with Vim, and knows only three different commands: “x”, “h” and “f”.

• “x” deletes the character at the cursor. The cursor position (counted from the left) does not change. Victor shall not use this command if the cursor is at the last character of the document.
• “h” moves the cursor one step backward (to the left). Nothing happens if the cursor is at the beginning of the document.
• “f” waits for the user to input another character C, and then moves the cursor forward to the next occurrence of C (even if the character at the cursor happens to be C). Nothing happens if C does not occur anywhere to the right of the cursor position.

For example, if the current text is

jeffiehadabigidea

where the cursor is denoted by a underline, then

• “x” would give jeffehadabigidea
• “h” would give jeffiehadabigidea
• “fi” would give jeffiehadabigidea

Write a program that calculates the least number of key presses that Victor needs to use to delete all the “e”s in the document, but no other letters. Initially, the cursor is at the first character of the document. Note that the “e” key is broken, so the command “fe” cannot be used.

입력

The first line contains the integer N, the length of the document. The next line contains N characters, each one of the ten lowercase letters from “a” to “j”. The first and the last letter of the input are both different from “e”. (N ≤ 70 000)

출력

The only line of output should contain exactly one integer: the least number of key presses Victor needs to delete all the “e”s.

힌트

An optimal solution for the example test case is:

fdhxhhxffhxfahxhhhxhhhxfdhxfghxfahhx

You can test this by starting the Vim editor yourself (type “vim file.txt” at the command prompt to open file.txt, type “:q<ENTER>” to quit).

35
chefeddiefedjeffeachbigagedegghehad

36