4 Keys Keyboard
Medium · Dynamic Programming · Math · Dynamic Programming
Problem
A special keyboard has four keys:
- A: type one 'A' on the screen.
- Ctrl-A: select everything on the screen.
- Ctrl-C: copy the selection into the buffer.
- Ctrl-V: paste the buffer after what is already on the screen.
You press keys exactly n times in total. Return the most letters 'A' that can be on the screen.
Examples
Input: n = 5 Output: 5
Press A five times. AA, Ctrl-A, Ctrl-C, Ctrl-V gives only 4.
Input: n = 7 Output: 9
AAA, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V: 3 + 3 + 3 = 9, more than the 7 that typing gives.
Input: n = 8 Output: 12
AAA, Ctrl-A, Ctrl-C, then three Ctrl-V presses: 3 + 3 × 3 = 12.
Constraints
- 1 <= n <= 50
Approaches
- Baseline: try every last copy point — time O(n²), space O(n)
Follow-up
Why does the window stop at five? A block of k - 2 pastes multiplies by k - 1 for k presses; splitting a long block into two shorter ones multiplies by more for the same presses. The use cases ask for the fewest presses to reach a target, and a keyboard where copying is a single key.
Related problems
Start free on Cariara · Coding problems · System design studio
