Connection Status:
Competition Arena > LexStringWriter

LexStringWriter

SRM 321 · 2006-10-02 · by Mike Mirzayanov

SRM 321 · 2006-10-02 · by Mike Mirzayanov · Dynamic Programming
Class Name: LexStringWriter
Return Type: int
Method Name: minMoves
Arg Types: (string)
Problem Statement

Problem Statement

You have a special machine called a LexStringWriter. It has a display that initially shows the String s, and the cursor's initial position is on the first letter of the string. The machine has three buttons: left, right, and enter. When you press left, the cursor moves one position to the left if possible. When you press right, it moves one position to the right if possible. The width of the display is exactly equal to the length of s, and the cursor can never leave the display. When you press enter, the letter shown at the current cursor position will be printed on paper, and that position on the display will be replaced with a space (' ').

Return the minimal number of button presses necessary to print all of the letters in s in alphabetically order. All occurrences of all letters in s must be printed, so if 'a' appears 3 times, for example, 'a' must be printed 3 times.

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • s will contain only lowercase letters ('a'-'z').
Examples
0)
"aaa"
Returns: 5

Press: enter, right, enter, right, enter.

1)
"ba"
Returns: 4

You should print the letter 'a' first.

2)
"abba"
Returns: 9
3)
"acbbc"
Returns: 12

Print the rightmost letter 'c' before the leftmost.

4)
"a"
Returns: 1

Submissions are judged against all 110 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LexStringWriter with a public method int minMoves(string s) · 110 test cases · 2 s / 256 MB per case

Submitting as anonymous