0
\$\begingroup\$

Given a string consisting of only printable ascii (letters, numbers, symbols, and spaces), how many keystrokes are required minimally to type out this string from scratch?

That is, current text is initially an empty string and should end up being equal to the input string. These are the allowed actions and their cost in keystrokes:

  • Add a character from printable ascii to the right-hand side of the current text
    (1 keystroke)
  • Ctrl-C copy any contiguous substring of the current text to the overwrite-only clipboard
    (2 keystrokes)
  • Ctrl-V paste the string last copied to the clipboard to the right-hand end of the current text
    (1 keystroke)
  • Backspace delete the rightmost character from the current text
    (1 keystroke)

For example, the string "cbaabcbabaacba" can be typed in 12 keystrokes, which is optimal.

cba => 3 keystrokes
<copy> => 2 keystrokes
ab => 2 keystrokes
<paste> => 1 keystroke
baa => 3 keystrokes
<paste> => 1 keystroke

Test Cases

cbaabcbabaacba => 12
ababcc => 6
aaaaaaaaaaaaa => 9
abcdefabcde => 9
abcdefabcdefabcde => 11
abcdefabcdefabcdefabcde => 12

Scoring

This is , so the shortest code wins!

\$\endgroup\$
19
  • 1
    \$\begingroup\$ Wait, Ctrl+C is two keystrokes but Ctrl+V is one? \$\endgroup\$ Commented Feb 6 at 13:55
  • 1
    \$\begingroup\$ @totallyhuman ctrl is still held down in theory \$\endgroup\$
    – pacman256
    Commented Feb 6 at 14:00
  • 1
    \$\begingroup\$ (1) Is the paste to anywhere or only at the right side? (As moving around the cursor is free for copy I would guess it is also free for paste, but probably worth stating definitively.) (2) Is backspace deleting of the rightmost character only, or any character again? (Also probably worth stating, the almost obvious, that backspace deletes.) \$\endgroup\$ Commented Feb 6 at 14:05
  • \$\begingroup\$ ...also probably worth adding an example (maybe how cbaabcbabaacba is achieved in 12). \$\endgroup\$ Commented Feb 6 at 14:06
  • 1
    \$\begingroup\$ @Arnauld abcdefabcdefabcde is 11 with both backspace and no backspace. \$\endgroup\$ Commented Feb 6 at 17:05

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.