Introduction

This classic optimization problem asks for the maximum number of A characters that can appear on screen after exactly N keystrokes, where the only allowed actions are A, Ctrl+A, Ctrl+C, and Ctrl+V. The key insight is that once N gets large enough, repeatedly typing A is no longer optimal and a copy-paste phase wins.

Why Greedy Intuition Is Not Enough

At first, typing A every time seems reasonable.

For small values of N, it is optimal:

• 'N = 1 gives 1'
• 'N = 2 gives 2'
• 'N = 3 gives 3'
• 'N = 4 gives 4'
• 'N = 5 gives 5'
• 'N = 6 gives 6'

But at N = 7, a better plan appears:

1. A
2. A
3. A
4. Ctrl+A
5. Ctrl+C
6. Ctrl+V
7. Ctrl+V

That produces 9 characters on screen, not 7. The reason is that after copying a block, each paste adds the entire copied block rather than a single character.

Dynamic Programming Formulation

Let dp[n] be the maximum number of characters possible with exactly n keystrokes.

There are two broad choices:

• press A and add one character
• at some earlier point, perform Ctrl+A, Ctrl+C, then use the remaining steps for Ctrl+V

If you stop at step b to prepare the clipboard, then:

• steps 1..b produce dp[b] characters
• step b+1 is Ctrl+A
• step b+2 is Ctrl+C
• the remaining n - b - 2 steps are pastes

That means the total becomes:

dp[b] * (n - b - 1)

The extra 1 comes from the original copied screen plus all pastes.

So the recurrence is:

1dp[n] = max(
2    dp[n - 1] + 1,
3    max(dp[b] * (n - b - 1) for b in 1..n-3)
4)

A Simple Python Implementation

1def max_as(n: int) -> int:
2    if n <= 0:
3        return 0
4
5    dp = [0] * (n + 1)
6
7    for i in range(1, n + 1):
8        dp[i] = dp[i - 1] + 1
9
10        for b in range(1, i - 2):
11            candidate = dp[b] * (i - b - 1)
12            dp[i] = max(dp[i], candidate)
13
14    return dp[n]
15
16for steps in range(1, 11):
17    print(steps, max_as(steps))

This prints the optimal answer for each step count. The algorithm is O(n^2), which is usually fine because interview and puzzle versions of the problem use modest values of N.

How to Think About the Best Breakpoint

The only interesting question is when to stop typing and switch to copy-paste. Every copy cycle consumes two setup keystrokes, so switching too early is wasteful. Switching too late misses the multiplication effect.

Dynamic programming works because it tests every possible breakpoint and remembers the best result for smaller step counts. You do not need a fragile rule like “always switch after four As.” The best breakpoint depends on N.

Common Pitfalls

• Forgetting that Ctrl+A and Ctrl+C each cost a keystroke and must be counted.
• Assuming the best answer for N = 7 is 8; the optimal result is 9.
• Writing a recurrence that counts only pastes and forgets the already copied screen content.
• Using a greedy shortcut without checking all possible breakpoints.
• Confusing “maximum after at most N keystrokes” with “maximum after exactly N keystrokes.”

Summary

• For small N, pressing A repeatedly is optimal.
• After a threshold, copy-paste beats direct typing.
• Dynamic programming is the standard way to solve the problem correctly.
• The recurrence depends on choosing the best breakpoint before Ctrl+A and Ctrl+C.
• A simple O(n^2) solution is usually enough for this problem.