Easy Problemsoptimizationlinear

Max A's using Special Keyboard

A keyboard has only four keys: type 'A', select all, copy, and paste. Given a fixed budget of n total key presses, find the maximum number of 'A' characters that can appear on screen.

Do this lesson first: house robber

Example input

n = 11 key presses

Expected output

27

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = max over j of dp[j] * (i - j - 1)

Ask where the last stretch of typing ended. Say the screen last grew by typing at press j. Everything after that is one select-all, one copy, and then nothing but pastes, because once you have copied there is no reason to type again: a paste is worth at least as much as a keystroke and usually far more. That leaves i - j presses, two of which are select-all and copy, so i - j - 2 are pastes. Each paste adds another copy of the buffer to a screen that already holds one, so the screen ends up multiplied by i - j - 1. Every choice of breakpoint j gives one candidate, and the best of them wins.

Everything up to six presses is a base case, and for a reason worth seeing rather than memorising: a copy-and-paste cycle costs three presses before it pays anything back, so on a small budget plain typing simply wins. dp[i] = i for i up to 6, and only from seven presses on does a breakpoint beat typing. Each computed cell reads a whole range of earlier cells, from dp[1] up to dp[i-3], so filling left to right guarantees all of them exist. Note the table's first cells are read constantly by later ones, unlike most tables here where each cell looks back only a step or two.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Everything up to six presses is a base case, and for a reason worth seeing rather than memorising: a copy-and-paste cycle costs three presses before it pays anything back, so on a small budget plain typing simply wins. dp[i] = i for i up to 6, and only from seven presses on does a breakpoint beat typing. Each computed cell reads a whole range of earlier cells, from dp[1] up to dp[i-3], so filling left to right guarantees all of them exist. Note the table's first cells are read constantly by later ones, unlike most tables here where each cell looks back only a step or two.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

i=9

i=10

i=11

0

1

2

3

4

5

6

9

12

16

20

27

maximum-as-special-keyboard.ts

1function maxA(n) {
2 const dp = [];
3 for (let i = 0; i <= n; i++) dp[i] = i;
4 for (let i = 7; i <= n; i++) {
5 for (let j = 1; j <= i - 3; j++) {
6 dp[i] = Math.max(dp[i], dp[j] * (i - j - 1));
7 }
8 }
9 return dp[n];
10}

Base caseComputedBeing readAnswer

The code, the trap, the variations

maximum-as-special-keyboard.ts

1function maxA(n) {
2 const dp = [];
3 for (let i = 0; i <= n; i++) dp[i] = i;
4 for (let i = 7; i <= n; i++) {
5 for (let j = 1; j <= i - 3; j++) {
6 dp[i] = Math.max(dp[i], dp[j] * (i - j - 1));
7 }
8 }
9 return dp[n];
10}

Where people go wrong

Assuming more copy-and-paste cycles always beat typing, and starting them as early as possible. A cycle costs three presses (select-all, copy, one paste) before it has gained anything at all, so on a short budget it loses outright, and even on a long one the best breakpoint is later than instinct suggests. The opposite mistake is just as common: assuming one cycle is always enough. It is not, for large n, and the recurrence quietly handles that because dp[j] may itself have been built by an earlier cycle.

The keyboard gains a cut key that clears the screen as it copies.
The multiplier changes but the split does not. You still ask where the last typing stretch ended; only the arithmetic turning dp[j] into a candidate is different. That is the useful thing to notice: the last-decision question survives, and only the combine step is rewritten.
You want the fewest presses to reach at least a target number of A's.
The optimization flips from maximize to minimize and the state changes with it: cells become indexed by A's reached rather than by presses spent. Same technique, transposed.

Permutations with K Inversions